Thanks to whose posted so far.
I'll post my specs but I'd like to emphasize that this is not a hardware issue, I should be able to run this at max fps.
There is no change in performance between any AA settings (2x decreases my fps exactly as much as Q16x). If it were just a hardware problem my videocard would be able to take 2x and I would see a decrease as I progressively went up.
The actual problem is more mysterious than that.
Specs:
CPU: Phenom 2 X4 955 OC'd to 3.8 GHz
GPU: GTX 275 OC'd
RAM: 3 GB DDR2
OS:Vista 32