build-essential: no installation candidate *sometimes*

Solution 1:

Ah, figured it out.

apt-get dist-upgrade
apt-get update
apt-get install build-essential

Fixed the issue.