Out of nowhere, several lines of warnings appeared during packages installation, the start of each line is always:

dpkg: warning: parsing file '/var/lib/dpkg/available' near line

To fix the problem, just run:

dpkg --clear-avail
apt-get update

Done.