I got a new Windows 7 machine, and was using VNC, SSH etc to connect to my Ubuntu machine, and it worked fine previously connecting to the Ubuntu computer's hostname. Now it doesn't work if I use the machine's hostname, but it does if I use the local IP or DynDNS name. I can also access it from my Android phone using the local hostname over SSH.

If I try to connect with SSH to the hostname, it says "Host does not exist". VNC says "Failed to get server address". NX says "no address associated with name", and I don't see it in Windows' "Network" folder.

I've rebooted everything. I've turned off Windows firewall. It was working fine a few days ago, but now it's not. How do I figure out what's blocking it?

Aha: It probably has something to do with Samba. I reset the Samba configuration the other day, and apparently this can affect it. http://ubuntu-virginia.ubuntuforums.org/showthread.php?t=1558925 I tried commenting out "encrypt passwords = No" as described there, but it still doesn't work.