The problem is one of:
1) Your refresh rate settings (VertRefresh and HorizSync) are set too low
2) Your video card doesn't have enough memory for a higher mode -- try lowering the color depth; if that works, then this is the problem
3) Something else
Posting your /var/log/XFree86.0.log file from the middle of a successful X session would help immensely...