Borre las ar y deje todos los repositorios como vos decías, hice el apt-get update y me tira:

dpkg fue interrumpido, debe ejecutar manualmente 'dpkg - configure-a' para corregir el problema

Lo mismo me hace cuando le hago el upgrade o el dist-upgrade

Luego vuelvo a hacer el sudo dpkg --configure -a y se me cuelga nuevamente en el mismo lugar:

Configurando hpijs (3.10.6-1ubuntu.10.2)...

No mueve de ahi. Tampoco puedo removerlo con remove