Corregir errores en la base de datos de paquetes de Debian

Llevaba unos dias con este error en una de las máquinas. Aparecía al instalar algún paquete con apt-get o haciendo alguna cosa con apt-cache


... in file '/var/lib/dpkg/available' near line 76438 package 'virtualbox-3.0':
error in Version string '3.0.14-58977_Debian_lenny': invalid character in revision number
...

Lo he corregido con:

dpkg --clear-avail
apt-get update