Thanks deepclutch but it turns out that the fglrx driver from ATI was fine, I just didn't install it properly. I thought that by apt-get installing it I would be cool with just typing 'fglrx' into the driver quotes in xorg.conf. No dice. When I checked the ATI Control Panel it listed my driver as Mesa instead of ATI. That was a dead giveaway that something was wrong.
Also, if I did startx from a console then logged out back into the console I would see an output from startx that said the fglrx module failed to load.
I finally got it working by installing mesa-utils, module-assistant, and fglrx-kernel-src.
I ran module-assistant to build an fglrx module:
# module-assistant prepare
# module-assistant a-i fglrx
I opened /etc/X11/xorg.conf and changed the driver to fglrx. I then added (underneath the driver line):
Option "VideoOverlay" "on"
I put this underneath:
Option "XVideo" "Enable"
Then I ctrl-alt-f1'd into a console and stopped gdm, unloaded the radeon module, loaded the newly created fglrx module and started gdm again.
I'm now able to suspend-resume on my nc6000 just as fast as my wife's new Core2Duo iMac does. Plus I can now easily use multiple displays which gives me a lot more nice things to show people that my GNU/Linux system can do.
I hope this helps someone else who's having trouble with this. If you have any questions about it please pm me as I may not be checking this thread frequently.