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?
Edit:
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.
Edit2:
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!