He said he had a 6670, not a 6770 so that's lower again. Your problem is simply a low-end graphics card for an unoptimized game. I used to have with a GTX 550 TI (which is better than the 6670) playing only at 1440x900 and it wasn't able to play GTA IV at max.
So ya, a graphics card upgrade is heavily due if you're expecting to play games at max nowadays.
a Radeon HD 6950 or 7850 would be fine??