I don't see you call SDL_SetVideoMode anywhere to get the screen surface, but I would make sure you are using double buffering.
The problem is actually here though:
TestThread = SDL_CreateThread(DrawAndUpdate,NULL);
//Update Screen
SDL_Flip(Screen);
I don't know how SDL_Threads work (I have never used them), but it looks to me like you are creating a new thread in every loop (which is bad for performance). It also looks like you never join or detach the thread, which makes me think you are leaking memory like nobody's business.
But the thing that is causing your particular problem is that you are flipping the screen in the main thread when DrawAndUpdate is happening in another thread. If DrawAndUpdate is only half done when SDL_Flip is called, you will only get half of your sprites on the screen. Without any sort of controls in place the behavior here is completely random. On some loops it will work fine, in others nothing will be copied before the screen flip. In short, put all your drawing code (including SDL_Flip) in a single thread, or at least wait until the drawing thread is finished before flipping the screen.