Ubuntu:
To uninstall VirtualBox Guest Additions on Ubuntu and similar operating systems, mount the virtual disk again that you used to install them - to do that, click on the Devices menu on the virtual machines top menu bar and select Install Guest Additions. If you get a pop-up about auto-start procedures just cancel it.
Now that the virtual disk is mounted, open a terminal and look for the contents of the disk in the /media folder.
ls /media
In my case, the disk is named VBOXADDITIONS_4.1.10_76795. This name may vary depending on the version of VirtualBox you have installed. Now uninstall the guest additions (don't forget to adjust the path):
sudo sh /media/VBOXADDITIONS_4.1.10_76795/VBoxLinuxAdditions.run uninstall
Windows:
You can uninstall the guest additions just like any other program on a Windows machine: Click on Uninstall a program in the Control Panel and search for the version you installed. Select it and click on the Uninstall button above the program list.