O espelho em suas fontes de software pode não estar atualizado. Tente mudar o espelho em fontes de software.
Experimente também o modo alternativo de instalação. Usando os comandos abaixo
sudo apt-add-repository 'deb http://toolbelt.herokuapp.com/ubuntu ./'
wget -O- https://toolbelt.heroku.com/apt/release.key | apt-key add -
sudo apt-get update
sudo apt-get install heroku-toolbelt