This bash script fixes the problem on fresh installs of ubuntu 12.04 installed as a VM on Proxmox, VMware or any container host. On fresh install apt is broken I have mainly seen this problem when installing VMs on OVH

Ubuntu apt fix

#!/bin/bash
rm /var/lib/apt/lists/* -vf
apt-get clean
apt-get -y autoremove
apt-get -y update
apt-get -y dist-upgrade 

apt-get clean
cd /var/lib/apt
mv lists lists.old
mkdir -p lists/partial
apt-get clean
apt-get update

apt-get -y dist-upgrade
apt-get -y install linux

echo "Fixed APT-GET"

exit 1