I'm having this exact problem as well. I have a Dlink DNS-323 attached to my network which just today became inaccessible using the network name \\DNS\ (yeah, I know, not a great choice, but it worked), and is now only accessible via IP. If I try the netbios name, I get the same errors everyone else does.
Of note: I just installed several updates today, and right after installing them, the problem appeared. Those updates were:
Security Update for Microsoft Office Publisher 2007 (KB969693)
Cumulative Security Update for ActiveX Killbits for Windows 7 Release Candidate for x64-based Systems (KB973346)
Windows Live Essentials
Update for Microsoft Office Outlook 2007 Junk Email Filter (KB971933)
Office Live add-in 1.4
Any help would be appreciated.