I've had this happen as well. It seems to work better to run dpkg directly rather than through apt-get.
Try dpkg -P <package>.
Also check man dpkg for forcing commands. Can't check right now, I'm in Mandrake which doesn't have dpkg.
Also do deborphan & apt-get clean.
deborphan | xargs apt-get -y remove
will clean out any stray files from other deletes. You will probably have to run it two or three times to get everything.
Hope this helps.