Question for those who have an install of 16.04 - if you type `hostname -f`, do you get the "command not found" error? I didn't have time to dig into it, but the man pages indicated that `-f` was still a valid option, but it appears that `hostname` was shifted to quasi-function.
I came upon this while trying to bring up my vagrant development box against 16.04, part of which was to set the hostname via `server.vm.hostname`.