Turns out you need to `apt-get update` all of a sudden...