To se mi taky stalo u jednoho balíčku.. no musí se holt rozbalit .deb soubor a jít po těch souborech, aby tam nic nezbylo. Pak je potřeba v souborech /var/lib/dpkg/status a /var/lib/dpkg/status-old najít záznamy o tom balíčku a ty odstranit. Potom už žádné utility jako třeba synaptic žádnou chybu hlásit nebudou a bude vše tak, jak má.