How to troubleshoot a hostname problem?

I have a Ubuntu desktop PC and a Windows 7 laptop. They have network connection over a wifi router, which gives them local IP addresses. Both computers see each other when pinged by IP. The Ubuntu pc can ping the Windows machine by hostname, but the Windows laptop can't ping the Ubuntu PC.

It looks like this is a common problem with a well-known solution, as seen from this question: Access server by host name?, as well as some duplicates. However, the solution there is "install avahi". I have avahi running, and it does not help for me. I have no idea how to troubleshoot from here.

From the Ubuntu PC:

rumtscho@bradbury:~$ sudo service avahi-daemon restart
[sudo] password for rumtscho: 
avahi-daemon start/running, process 3019

and then on the Windows laptop:

C:\Users\rumtscho>ping bradbury.local 
Ping-Anforderung konnte Host "bradbury" nicht finden. Überprüfen Sie den Namen, 
und versuchen Sie es erneut. 

which means, roughly, "hostname not found".

I didn't find anything suspicious in avahi.conf. Here are the working lines of the file (everything else is commented out):

[server]
use-ipv4=yes
use-ipv6=yes

[wide-area]
enable-wide-area=yes

[rlimits]
rlimit-core=0
rlimit-data=4194304
rlimit-fsize=0
rlimit-nofile=768
rlimit-stack=4194304
rlimit-nproc=3

I tried both pinging bradbury and bradbury.local. I also tried uncommenting the line publish-addresses=yes in the conf file. Both didn't work.

Any ideas what I am doing wrong? How can I find it out, what are my options?

Update I was told in chat that the Windows PC needs a "multicast DNS resolver", so I installed Bonjour. Now the error message is different:

Ping wird ausgeführt für bradbury.local [*IPv6 address edited out*] mit 32 Byt
es Daten: 
Zielhost nicht erreichbar. 
Zielhost nicht erreichbar. 
Zielhost nicht erreichbar. 
Zielhost nicht erreichbar. 

Ping-Statistik für *IPv6 address edited out*: 
    Pakete: Gesendet = 4, Empfangen = 0, Verloren = 4
    <100% Verlust>,

"Zielhost nicht erreichbar" means "cannot reach target host", and there is 100% packet loss. So what should I do to make the Ubuntu PC reachable

Avahi is a zeroconf/bonjour DNS responder, which is not available per default on Windows since its an Apple invention. It may help if you install 'Bonjour for Windows' on the W 7 machine.

If you don't like this, the Windows laptop can resolve your linux desktop if the desktop runs samba, the nmbd daemon there will advertise the hostname and the corresponding IP-Address by means of NetBIOS over TCP/IP, which is just a checkbox somewhere in the Windows networking preferences.

The router may do IPV4 only, perhaps disable IPV6 on both, reboot Windows, retry. Also, avahi may not pick up config changes immediately, do a restart avahi as root.