How to fix: VirtualBox Guest Additions setup is out of date

When you are trying to install/update VirtualBox Guest Additions on your guest machine but the setup is for a different/older version (for example 4.0.4 tools for a 4.1.x VirtualBox installation), try this:

sudo apt-get install virtualbox-guest-additions-iso

For some reason, this is no dependency to VirtualBox itself -- and if you have an old ISO lying around, VirtualBox will just pick that one, regardless of its version.

Oh joy.