Consegui resolver o problema....
Descobri que o arquivo available da pasta /var/lib/dpkg/ havia sumido, e nesse mesmo diretorio estava um available-old, não sei se isso é recomendado, mas apenas renomeei esse arquivo para apenas available, e agora deu certo!
Agradeço...