I've been having a very similar problem. However, it is with a cupswrapper.
justin@justin-desktop:~/Desktop$ sudo apt-get remove dcp130ccupswrapper
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: The package dcp130ccupswrapper needs to be reinstalled, but I can't find an archive for it.
I've tried dpkg, force and such but to no avail.
Unlike Mark, I do not have /etc/init.d/lpd