If things get messy and you weren’t able to remove it using the package management tool (apt-get or aptitude), then you can manually remove the package:

Open /var/lib/dpkg/status as root, “sudo gedit /var/lib/dpkg/status” and search for your package and remove the whole block.