Try upgrading the security on the NAS if you can. I was having trouble with my SMB shares untill I raised the security to include password encryption. If you can't up the server's security, you can down grade windows' through the local security policies.
Local Policies > Security Options >
1. Network Security: LAN Manager Authentication Level > Send LM & NTLM responses (Win95/98 level)
Send NTLM responses only (early Win NT/XP level)
2. Network Security: Minimum security for NTLM SSP based servers/clients > Uncheck both options
There are similar complaints about this problem all over the internet, especially with wireless connections. I believe that the wireless security encryption is also part of the problem.