If you search for guides for changing the size of VirtualBox .vdi disks, there are plenty, and really the solution is pretty simple, just
vboxmanage.exe modifyhd "<path-to-vdi>" --resize <newsize-in-MB>
But what some of the guides fail to mention (some of them don’t fail to mention it, but since you are reading this post you probably failed to see it in the guides that did mention it) is that you really should delete all the snapshots for the disks you are trying to change the size of, BEFORE changing the size. Otherwise you’ll pretty quickly notice that the guest OS doesn’t recognize the drive size change, and now you can’t delete the last snapshot, getting instead the error with something about “virtualbox could not merge the medium VERR_INVALID_PARAMETER”.
So this post is really for you that are now stuck with a virtual machine that has a disk that cannot be size-changed and a snapshot that cannot be deleted.
Basically the solution is to clone the whole virtual machine using the standard virtualbox functions, because the cloned version will be free of any snapshots and still represent the current state of the original VM.
When you are going to clone it you will be presented with some options which are self-explanatory. But one of those options will have you choose to keep or discard all the snapshots, and you obviously have to choose discard at that point.
One small drawback of this operation is that VirtualBox does not seem to let me choose where to put the disk of the cloned machine and creates it in the default location, which can be problematic if you keep your disks somewhere else.
Now you will still have to resize the new disk. This is where another small problem arises: if you just use the command line fromt he beginning of the post on the newly created disk, you may receive the error “VBoxManage.exe: error: Cannot register the hard disk … becase a hard disk …. with UUID … already exists”. Long story short, the solution is to first run
vboxmanage.exe internalcommands sethduuid "path-to-the-new-disk"
It will assign a new uuid to the disk which will solve the problem, and you can now resize the disk with your normal command (the modifyhd one, from the beginning of the post).
Now just boot into the guest and use Gparted (if you have *nix) or Computer Management -> Storage -> Disk Management in Windows 7 (probably Vista had this already) to make the guest OS understand the new disk change.
Of course, now would be also a good time to make sure the guest OS works properly and delete the original VM in VirtualBox gui to save space.