Então, depois de tentar vários comandos no terminal para tentar forçar a remoção, finalmente consegui descobrir que o pacote não estava completamente instalado. Então eu abri o arquivo DEB, copiei o resto dos arquivos, e usando o "gksudo nautilus" para obter acesso root, eu colei o resto dos arquivos que incluíam a pasta que o erro mencionado estava faltando. Então o Synaptic conseguiu consertar o pacote e eu pude removê-lo permanentemente.