Recently I had this issue with a Debian server.
apt-get autoremove broke some packages and I was not able to remove them either with apt-get remove, dpkg -P or dpkg –remove –force-remove-reinstreq
What I did was the following:
- cd /var/lib/dpkg/info
- rm package_name.*
- dpkg –purge –force-remove-reinstreq
Then everything was neat 😉