I've had this issue too, apparently it used to completely fail if the hostname lookup failed even if your sudoers didn't talk about hostnames at all: https://bugs.launchpad.net/ubuntu/+source/sudo/+bug/32906