I have had this problem with a couple of games, it turned out to be a memory problem.
When I reset the machine and boot into windows there was a lot more memory available and games run perfectly. But if I had been using the pc for a while doing other stuff or playing other games I was getting problems because the FREE memory wasnt enough to run GTA.
This is on Vista. Closing the sidebar gives me back quite a lot of FREE ram.
GTA 4 caused me big problems like this and I was running Vista x64 with 4gb ram.
Now I'm running Vista x64 with 8Gb ram and have no problems at all. Dont even have a swap file which makes windows run a lot faster.