Bug#581216: Fix for this bug
I got it working after modifying xorg.conf and installing the firmware. Install firmware-linux (which includes the non-free firmware files) and reboot the PC to get the firmware to load. This managed to get X to start, but it picked a bad resolution for my ThinkPad LCD and the screen was garbled. I had this same bug with Ubuntu 8.04/8.10 and had submitted a bug report to Ubuntu for this same problem. I dug up the xorg.conf that fixed my problems and switched to it, now X and GNOME work perfectly!
Here's a link to the xorg.conf http://launchpadlibrarian.net/34916180/xorg.conf (for IBM ThinkPad A21p, or modification for any Rage 128 chipset).