Ok it turns out I had 2x AA on and 4xAF. I turned AA of and turned Bilinear filtering on, and now I average about 70fps, and about 25fps when recording with FRAPS.
I also wasn't using half-screen recording with FRAPS, so that was messing up the videos and making them seem slow-mo. I switched to half-screen and now they work great, except it won't record sound.
So I'm pretty satisfied with it now, but if I was to upgrade, which component do you think I should upgrade?