Por alguns motivos, o arquivo /var/lib/dpkg/available está danificado.
Afaste-se, por exemplo, com
sudo mv /var/lib/dpkg/available /var/lib/dpkg/available.bak
Se houver um arquivo /var/lib/dpkg/available-old tente se este funciona:
sudo cp /var/lib/dpkg/available-old /var/lib/dpkg/available
Se a instalação do software funcionar agora, você está pronto.
Se ainda não funcionar, execute
sudo rm /var/lib/dpkg/available
sudo sudo touch /var/lib/dpkg/available
sudo sh -c 'for i in /var/lib/apt/lists/*_Packages; do dpkg --merge-avail "$i"; done'
para criar um novo arquivo.