If you just uninstall the desktop packages and/or gdm, you will find that your system will hang upon reboot: it's trying to start a gdm that's not there!
First, this is braindead behaviour from Canonical/Ubuntu. Uninstalling GDM should obviously clean up after itself, including setting a new default display manager, or if there is none, then change to boot to text mode.
Here's what you have to do *before* you reboot. (else, you boot into a rescueCD):
edit /etc/default/grub, and change this line:
Then, run "sudo update-grub". (If and only if you are in a rescueCD, then you have to edit /boot/grub/grub.cfg so that the default menu option has init=/bin/bash at the end of the kernel load line; reboot, remount / read-write, run "update-grub", and then reboot.
Failing that (or if you want to be sure), verify that the file /etc/X11/default-display-manger is empty (or the one line is commented out).