On trusty, the hostname was not in /etc/hosts and it was working fine. The real issue here is that sudo looks into DNS before hostname.
In /etc/nsswitch.conf, we had on trusty: hosts: files myhostname mdns4_minimal [NOTFOUND=return] dns
We now have: hosts: files mdns4_minimal [NOTFOUND=return] dns myhostname
On trusty, the hostname was not in /etc/hosts and it was working fine. The real issue here is that sudo looks into DNS before hostname.
In /etc/nsswitch.conf, we had on trusty:
hosts: files myhostname mdns4_minimal [NOTFOUND=return] dns
We now have:
hosts: files mdns4_minimal [NOTFOUND=return] dns myhostname