godai73 - thanks a lot for your time and thoughts on this issue. To answer your questions:
"can you try to manually map to the server?"
No - I get "the network path '\\servername' could not be found".
"Can you also do a search for the computer using the Find/Search option under the Start Menu?"
No luck.
"Does your user account have permission to access the server?"
Yes, I'm in the Administrator group. It's just a matter of browsing through My Network Places. I can connect via Enterprise Manager, Terminal Services, through web pages, etc., just not through My Network Places. This hasn't been a big deal until recently. My new backup software requires that I browse to the server through My Network Places and won't let me just enter the server name or IP address.