Ya consegui, al fin, encontrar la solcución.
Mirando la referencia de debian vi que en var/lib/dpkg hay un archivo llamado available donde estan todos los paquetes y una sección de
Depends: con el nombre de las librerias de las cuales dependen, he borrado el nombre del paquete pero aun no funciona.
El archivo que se tiene que modificar era el "status" de la misma carpeta.
Con apt-get no funciono (supongo que tenia que reeleer el archivo) pero dpkg lo elimino sin problemas.
Gracias a los dos por tomarse la molestia en responder.
EDITO: Ahora acabo de ver que rompia los paquetes