I seem to be having the same problem as art555.
My specs are:
Microsoft Windows XP Home Edition
Service Pack 3
Q6600 @ 2.4Ghz
XFX 8600GT @ 621/1336/453 (quite serious overclocking from 540 to 621, i have to admit it.

)
Driver: 182.06
2 GB's of RAM @ 667Mhz.
Everything set to low, 800x600 (with a 22'' screen)
the FPS really differs, the best weather setting for playing it is a sunny day, and it's worse at night, when it's raining.
The fps never goes over 25, and it seems to be really laggy and unstable.
Unfortunatly, the newest patch isn't working at all for me, even with a freshly installed GTA IV.
This really annoys me as the recommended settings clearly said the 8600GT was good enough. Velociround is right.
I'll try downclocking to the normal Clocks, however i don't think it will make a difference.