abra o pacote .deb novamente e olhe o nome real da instalação dele, exemplo: Se você tenta instalar o Sun xVM VirtualBox o nome real do pacote é virtualbox-2.2.
Assim que verificar o nome real do pacote, abra o terminal, logue como root e excute um apt-get remove NOMEDOPACOTE.
Pronto, pacote removido com sucesso, espero ter ajudado.