I have been trying for a couple of days to get my system to display something higher than 800x600. I have a Matrox Millenium II card (which I know supports higher resolutions) and a 21" SGI GDM-5411 monitor. 800x600 on 21" monitor is killing me.
My xorg.conf is
_________________________________________________________
# XFree86 4 configuration created by pyxf86config

Section "ServerLayout"
Identifier "Default Layout"
Screen 0 "Screen0" 0 0
InputDevice "Mouse0" "CorePointer"
InputDevice "Keyboard0" "CoreKeyboard"
EndSection

Section "Files"
RgbPath "/usr/X11R6/lib/X11/rgb"
FontPath "unix/:7100"
EndSection

Section "Module"
Load "dbe"
Load "extmod"
Load "fbdevhw"
Load "glx"
Load "record"
Load "freetype"
Load "type1"
Load "dri"
EndSection

Section "InputDevice"
Identifier "Keyboard0"
Driver "keyboard"
Option "XkbModel" "pc105"
Option "XkbLayout" "us"
EndSection

Section "InputDevice"
Identifier "Mouse0"
Driver "mouse"
Option "Protocol" "IMPS/2"
Option "Device" "/dev/input/mice"
Option "ZAxisMapping" "4 5"
Option "Emulate3Buttons" "yes"
EndSection

Section "Monitor"
Identifier "Monitor0"
VendorName "Monitor Vendor"
ModelName "GDM-5411"
DisplaySize 400 300
HorizSync 30.0 - 121.0
VertRefresh 48.0 - 160.0
Modeline "1280x960@75" 142.76 1280 1312 1848 1880 960 978 990 1009
Option "dpms"
EndSection

Section "Device"
Identifier "Videocard0"
Driver "mga"
VendorName "Videocard vendor"
BoardName "Matrox Millennium II"
EndSection

Section "Screen"
Identifier "Screen0"
Device "Videocard0"
Monitor "Monitor0"
DefaultDepth 24
SubSection "Display"
Viewport 0 0
Depth 24
Modes "800x600" "640x480"
EndSubSection
EndSection

Section "DRI"
Group 0
Mode 0666
EndSection
__________________________________________________________

I have tried adding other modes like 1024x768 in the Screen section with color depths of 16 and 24. The system takes it, tells me I need to reboot, then upon reboot its back like it was at 800x600 with those resolutions no longer accepted.
I also added the modeline in the diplay section, but it does nothing.

What distribution are you using? Perhaps there is some auto-hardware detection utility being run during bootup which is overwriting your xorg.conf.

Also, what desktop environment are you using (if any)? KDE will meekly accept whatever resolution is handed to it, while GNOME will thickheadedly insist upon what resolution it was last set at.

In any case, it's easy to restart your x server without fully rebooting your system. First, quit any programs your running (because they'll be rudely interrupted when you yank away the x server from them). Then press Ctrl-Alt-Backspace. If you're using a graphical login manager (like kdm or gdm), then you'll log out also and have to log back in.

If there's some auto-hardware detection utility which is overwriting your xorg.conf during bootup, this technique to only restart the x server should bypass it. Then, you'll have to figure out what utility is doing the offensive rewriting and deactivate it.

I'm using Fedora Core 2 and I'm running Gnome. If KDE will more readily accept the resolutions, I will switch.

How would I go about finding the utility thats changing it?

Fedora has a great utility for setting display.
In FC2 open a Konsole and enter

system-config-display

Set your display where you want it.

That's assuming you don't have other issues like driver problems.

I have been there. Thats the same utility thats in the application menu on Gnome. My only option there is 800x600 and 640x480. The video card is set correctly, and the monitor is correct. I looked up the specs for that monitor and they are set correctly in the xorg.conf.