Can you ping the NAS by the hostname? Try the command "getent hosts hostname", using the hostname of the nas.
Netbios styled hostnames and real hostnames aren't exactly the same animal. Make sure that you don't use any characters that are legal for one but not the other. No underscores IIRC but minus signs are OK. No periods in the hostname itself. That would make the hostname look like a FQDN.
Also, is the hostname present in your /etc/hosts file. If it isn't perhaps you used the avahi dns daemon in your previous distribution, but not in this one or it isn't running. If it is running you can try pinging like "ping hostname.local".
Make sure that you have the ports open that you need. The name service for smb uses 137/UDP. Opening 137/TCP and forgetting to open the UDP ports is a common mistake. Even running nmap against a machine without options, you could miss the problem.
Code:
netbios-ns 137/tcp # NETBIOS Name Service
netbios-ns 137/udp # NETBIOS Name Service
netbios-dgm 138/tcp # NETBIOS Datagram Service
netbios-dgm 138/udp # NETBIOS Datagram Service
netbios-ssn 139/tcp # NETBIOS Session Service
netbios-ssn 139/udp # NETBIOS Session Service
...
microsoft-ds 445/tcp # Microsoft-DS
microsoft-ds 445/udp # Microsoft-DS
At home, because I only have about 6 addresses needed (including router, printer, external drive) I added the MAC address / IP address values to my router. This enables me to add all of the devices to the /etc/hosts file, and not have an IP address change when the lease runs out or the router is reset. I found that resolving names using the avahi daemon (zero config in Windows, Bonjour on the Mac) was to slow. For a larger network, I would probably run the dnsmasq daemon instead to avoid maintaining an /etc/hosts file for each computer.