It turns out it is a Samba configuration issue, easily solvable but poorly publicized.
- (Uncomment and) change name resolve order in Samba configuration:
sudo gedit /etc/samba/smb.conf
name resolve order = lmhosts bcast wins host
- Restart Samba
sudo /etc/init.d/samba restart
- Browse your shares (may be you have to wait some minutes before doing this).