I've gotten the message on my home network on an Ubuntu system with a dynamically assigned IP address from a router providing a combined DHCP and DNS server for my network.
hostname: Name or service not known can be caused by such a device going down, if only for an instant.
For example this can happen if my home router is rebooted when my power goes out.
The problem here is that the DHCP service your network is relying upon forgets all of the IP addresses it has assigned and the associated domain names. When your computer checks the associated dns server for its own name the server no longer has it. Some DHCP servers may avoid problems by writing the assignments they have made to their disk or flash memory so nothing is lost when they restart.
The server may ordinarily take your computername from your systems DHCP request, make it computername.local and store that in its records, making it available in its associated DNS server simultaneously. Usually
hostname -fqdn requests the full domain name over your network from your DNS server and if it has the record it will return that name. The
.local suffix makes it look like a valid fully qualified domain name (though it isn't really a valid global domain name). This is why you may not have to specify a domain name manually in /etc/hosts or /etc/hostname files.
The DHCP server restarting may cause further problems as IP addresses may be assigned to multiple computers simultaneously, causing some not to be able to communicate. The address is assigned once before the server restarts, and again after it does.
If your DHCP server forgets its assignments the safe thing to do is to reconnect each computer it serves when it restarts. When I lost mine I simply disconnected and reconnected to my wifi access point. On a wired network you can use
ifup or simply disconnect and reconnect the network cable.
When reconnecting my system automatically uses dhclient to get a new address--my computer and the server now agree on who I am, and the message no longer appears.
If you wait long enough the DHCP lease will timeout and your system will ask for and get a new lease from the server--clearing up the problem. This will probably be hours or days later (for my server it is one day).
If you have defined a static IP name and address and if the DNS reverse look-up records are correct the problem shouldn't happen.