I tested again using rdesktop on Squeeze, and could reproduce the problem. These were the messages printed by celestia when it died:
*** Cannot find the double-buffered visual. *** Trying single-buffered visual. *** No appropriate OpenGL-capable visual found. -- Happy hacking Petter Reinholdtsen -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org