I just noticed some other things that may be pertinent. Note that this is occurring on two 32-bit systems and one 64-bit, none of which have had any changes made to them beyond installing some apps that I like (chrome-unstable, gftp, pan, Sylpheed, gmail-notifier).
Not only does the problem with Synaptic noted above occur on all three installs, but I've also just noticed that if I go to "Custom Filters" and then pick "Missing Recommends" there are a ton
of them. A "ton" is approximately 100.
Some of these are kind of strange, like it says I'm missing gdm. Another was the apt-xapian-index. Others include fast-user-switch-applet, fcron, fetchmail, and exim4.
I'm thinking this list isn't completely correct, as I have a nice Gnome desktop even though gdm is "missing," and I presume that's because I have gdm3 instead.
If these other things are truly recommended and not installed, I'll repeat that I haven't removed anything. They must have been missing from the start (on three distinct installations). Can anyone confirm that they also see a bunch of these "Missing Recommends"?