Despite the listing it seemed to have removed everything ok except for removing a line it added to /etc/dhclient-exit-hooks. I had no other lines in this file except the one added by firestarter so I just moved the file out the way and ran the purge again. This time it completely without issue.
I just had this problem purging firestarter.
These were the files left behind for me
$ dpkg -L firestarter exit-hooks r/non-routables d/firestarter
/etc/dhclient-
/etc/firestarter
/etc/firestarte
/etc/init.
Despite the listing it seemed to have removed everything ok except for removing a line it added to /etc/dhclient- exit-hooks. I had no other lines in this file except the one added by firestarter so I just moved the file out the way and ran the purge again. This time it completely without issue.