It is an old question, but I hope that I still can help some people who are stuck on this issue.
On, for example, Ubuntu you can do the following:
Open the following file: /etc/nsswitch.conf
nano /etc/nsswitch.conf
Change this line:
hosts: files dns
To:
hosts: files wins dns
Then install winbind:
sudo apt-get install winbind
Note: if you already have samba installed, you may find winbind is already enabled.
Check that the winbind
service exists and is enabled:
sudo systemctl status winbind.service
You can enable the service as follows:
sudo systemctl enable winbind.service
Now your Linux hostname can be resolved on your Windows PC.
To find out what your hostname is on Linux use:
hostname