mDNS (Avahi) not working when hostname changed

Question

With a new Raspbian Jessie 4.4 (4.4.38+ #938 Thu Dec 15 15:17:54 GMT 2016 armv6l GNU/Linux) OS installed and ssh enabled it is possible to access the machine with:

$ ssh [email protected]

However if the hostname is changed in /etc/hostname (and /etc/hosts), for example to new_hostname01 (from raspberrypi), it is no longer accessible using ssh pi@new_hostname01.local.

$ ssh pi@new_hostname01.local
ssh: Could not resolve hostname new_hostname01.local: nodename nor servname provided, or not known

Both machines are connected to the network (can access the internet and previously each other). I can't find any obvious tutorials or configuration to change. There are several mentions of the old hostname raspberrypi in /etc/ssh/ as the keys for the machine. I deleted them all and successfully regenerated them with this answer. I also reloaded the avahi-daemon with sudo avahi-daemon -r and tried rebooting the whole machine but so far I have always got the same error.

Additionally the advice about finding other computers on the network does not yield anything from Raspbian with changed or original raspberrypi hostnames.

(I'm posting here instead of on raspberrypi.stackexchange as it would make sense if this is a general ssh networking on Unix/Linux issue rather than one specific to Raspbian. Happy to move it if it turns out otherwise.)

Answer 1

Install avahi-utils and then run (as suggested here):

$ avahi-browse -arp

This reported multi devices including:

+;wlan0;IPv4;newhostname01\032\091d4...\0580d\093;Workstation;local
=;wlan0;IPv4;newhostname01\032\091d4...\0580d\093;Workstation;local;newhostname01.local;192.168.0.40;9;

Trying to ssh [email protected] works.

It seems host names with underscores are not allowed which makes sense as according to this answer, rfc1123 does not allow underscores in host names.