Xenial (16.04) cannot find package libboost-all-dev
Try adding the repository (http://packages.ubuntu.com/search?keywords=libboost-all-dev)
sudo add-apt-repository universe
sudo apt-get update
sudo apt-get install libboost-all-dev
Another sudo apt-get update and then it worked.
Possibly that update needs to come after add-apt-repository universe.