When I ran
sh /media/cdrom/VBoxLinuxAdditions.run I got the following warning message:
You appear to have a version of the VBoxGuestAdditions software on your system which was installed from a different source or using a different type of installer. If you installed it from a package from your Linux distribution or if it is a default part of the system then we strongly recommend that you cancel this installation and remove it properly before installing this version. If this is simply and older or a damaged installation you may safely proceed.
How do I uninstall the VBoxGuestAdditions that was a default part of Debian?
After reading and trying out jw013's answer, I suspected that maybe I just didn't know the proper package names. I did a bit more searching, and found out that I can see the list of packages installed by running
dpkg -l. So I ran
dpkg -l | grep virtualbox
then I got
ii virtualbox-ose-guest-dkms ... ii virtualbox-ose-guest-utils ... ii virtualbox-ose-guest-x11 ...
Then I removed each manually by running
apt-get remove virtualbox-ose-guest-dkms virtualbox-ose-guest-utils virtualbox-ose-guest-x11
So far it looks like that might be the solution, though it's weird because when I run the command it wants to install 38 new packages, most of them with xserver related stuff.
I tried the above with a fresh install (reasonably minimal install -- used the businesscard.iso with nothing marked when tasksel came up) then followed the directions here, and everything worked perfectly!