Linode explains pretty well how to change the hostname of your VPS. But they do not mention that in the latest Ubuntu it is set via Linode`s own DHCP server. So even if you set it via /etc/hostname and in hosts, it will still be overwritten by Linode`s own hostname given to your server.
The solution is to kindly thell DHCPCD to *not* override the hostname you have set, open /etc/default/dhcpcd and alter the following:
Reboot and voila! 🙂