Noted here for posterity: I recently had Ubuntu 10.10 (lucid) upgrade my kernel to 2.6.35-28, and on the next boot, the X server failed to start. It just hung indefinitely with a purple screen, and the X server log didn't contain anything terribly informative.
It took a lot of googling, but I eventually came across this post which identifies the root cause: I installed the new (experimental) gold linker on my system several weeks earlier. It seemed to work well with all my C++ projects, and is a good deal faster than the standard ld.
It turns out there is a well-known limitation with gold right now: it can't compile a working kernel. This also seems to apply to installing the nvidia kernel module against an upgraded kernel. Resolved it by booting in rescue mode to a root shell and running:
# aptitude remove binutils-gold # dpkg-reconfigure nvidia-current
Thanks to Jesse Vogt for posting his description, it would've taken me a while to connect the dots between binutils-gold and that error!