Interesting tidbit about Postfix and Amavis, particularly when Debian distribution upgrades come into play: if amavisd can't be contacted, messages may become stuck in the queue.
postsuper -r ALL will requeue all messages, fixing the situation. See this forum post, which tipped me off to the whole thing. I don't think the situation described there matches my problem, but the solution sure worked! At least, after I made sure amavisd was running, since it wasn't. I will update this post if I get any more information.
On a somewhat related note, when Aptitude wants to remove packages, you should probably do a quick check to make sure it's not trying to remove anything important, like your DHCP client.