Synaptic is stuck - removing partially installed package?

[Chanchao]

Something went wrong installing VirtualBox... Someting about a wrong
kernel version even though I use plain Edgy (386 kernel.. perhaps it
expects 'generic' -- anyway)

Result is that I can't use Synaptic or apt-get for anything anymore, not
even removing VirtualBox!!

This is what happens:

$ sudo apt-get remove virtualbox
Reading package lists... Done
Building dependency tree       
Reading state information... Done
E: The package virtualbox needs to be reinstalled, but I can't find an
archive for it.

And that's it...  I'm stuck. Also Automatic Updates don't work anymore. 

Any clues?

Cheers,
Chanchao