Thanks @tom for your solution above. Important update that I suggest you integrate into your post above:
Change:
sudo apt-add-repository -y 'deb http://ppa.launchpad.net/ondrej/mysql/experimental/ubuntu precise main'
To:
sudo apt-add-repository -y 'deb http://ppa.launchpad.net/ondrej/mysql-experimental/ubuntu precise main'
(change is mysql/experimental -> mysql-experimental)
Without this, I was getting issues like this one:
W: Size of file /var/lib/apt/lists/toolbelt.heroku.com_ubuntu_._Packages.gz is not what the server reported 721 724
And the build would fail at the apt-get update step.