After a few days of not being able to restart X, I started turning things off that might have caused the video card to do something unexpected. I was able to get X to restart properly by disabling radeonfb. I'm not entirely sure why, but if you are using the radeon framebuffer included with the kernel, fglrx starts acting strange.
How to fix it:
Remove radeonfb support from your kernel. The VESA framebuffer will work fine.
In 2.6.17 the framebuffer options are located in
"Device Drivers --> Graphics Support"
If you have it compiled into the kernel and don't feel like rebuilding you can add
to your kernel arguments to disable it.
Hope this helps.