Estranhamente, apenas a reinstalação do Ubuntu Server 16.04.1 ajudou. Então, eu não instalei
libboost-all-dev
mas apenas os pacotes exigidos pela Trinitycore. Agora
make
é executado após o cmake sem nenhum problema.
Adicionando as opções
-DBoost_<missing package>_RELEASE=/usr/include/boost/<missing package>/
cmake pode encontrá-lo. Estranho, porque estes são apenas subdiretórios de
/usr/include/boost
que já foi encontrado pelo cmake.