upgrading from 15.10 to 16.04 apt not installed
Had the same problem, solved by forcing the update of apt and cleaning the current installation as Andrew suggested:
sudo apt-get update
sudo apt-get upgrade
sudo apt-get -f install # (not "install -f"!)
sudo apt-get -y install apt
sudo do-release-upgrade
I had this error, for me I was missing the wily-updates line from my /etc/apt/sources.list:
deb http://archive.ubuntu.com/ubuntu/ wily-updates main restricted universe multiverse