1) Put all your tiles on a bigger sheet, and remember where they are, so you can figure out what their coordinates are. Bascially you should have a list that has every material, and what coords it was assigned on the sheet.
2) Make a data structure that consists of 4000 quads (or however many you need for you map, I'm using 4000 because you said 4000). GO find a tutorial somewhere that will tell you how to make one, or use a modeling application. Remember that each quad will need it's own set of uv coords. They can't be shared.
struct quad
{
vector3 [4] vertex;
vector2 [4] uv;
}
3) Go through the quads and assign them the uv coords from your texture atlas. Refer to the list from step one.
4) Use XNA to create a vertex object out of your data from your struct.
5) When drawing, load the tiles texture atlas, and then just draw your map out in 1 call, as one model.
Drawing your map til by tile means you are sending over 4000 draw calls per frame. That's about ~3500 too many!