I think the time is right for a push to get XEphem back into Debian. The immediate problem is that x11-common has added a Conflicts: against xephem without any version specifier. XEphem hasn't been in Debian for a while now, but there are a couple of independently packaged versions -- since they're all named "xephem" this causes problems for those packages, too.
The original difficulty is that XEphem ships with a modified form of the Yale Bright Star Catalogue, which violates the license on that dataset. Since nobody stepped up to prepare a distributable version, e.g. using a freely distributable star catalogue, it was dropped after Woody. The new conflicting x11-common seems to have spurred some interest (bug discussion), and there does exist (for example) an EDB of the Hipparcos stars that would work legally. Apparently the Ubuntu users already knew this.
Longer term it would make sense to integrate XEphem into the stardata-common work by Kevin McCarty et al, which really shouldn't be too hard. If we're going to put in that sort of effort, it shouldn't be much work to create free alternatives to the planetary surface images and other extras distributed with the commerical version of XEphem, either.
Which brings me around to another tangent: given what an enormous pain such packages can be, wouldn't it make Debian a natural choice for astronomy if one could Debianize the installation and maintenance of things like Aips and IRAF? Someday I might be inspired to think about such horrors.