I've got workarounds for most of the problems that it presents, so none of the Network people are giving me much time at the moment (they're too busy with moving the company over to Oracle financials at the moment).

Anyhow, I would think that if it were a DNS problem, that it would be inaccessible by name from other boxen as well. Looking at the 'Directory', I can see that the server shows up in the Domain and can be managed from there. But looking under the 'Microsoft Windows Network' for the same domain, the server doesn't show up.