I'm getting only about 20 fps on medium settings. (Ubersampling is turned off, latest drivers, and no 3D drivers).

3.2 Ghz Quadcore Amd
8 gigs of RAM
Nvidia 8800 GTS 1gig

Checked CPU load during the game, it's only at %20.

Check GPU load, with something like MSI Afterburner. You'll probably see 98-99%.

That's a minimum-spec card(!) It'll do medium settings at reduced resolution, at frame rates in the 30's. It will have frame rate problems trying to do medium settings at full resolution.

My res is roughly 1400x 1200. Even at low settings I can't get past 24

It suggests something else in your computer is interfering with the game.

I have a somewhat lesser setup, with an 8800 GTS 512, Phenom II x3, 4GB RAM, and Vista, and I get consistent 32-33 fps at 1440x900.

Have you run MSI Afterburner to see what the actual load on the GPU is? Do you have an adequate power supply (all flavors of 8800 were pretty power-hungry), and is the auxiliary connector hooked up?

500 wats and yes.

Does it do this with every game or they this one. Could be heat as well.