The server will have a netbios name, which is independent of DNS. That's why I asked whether Explorer saw it by name rather than dotted.quad.
It just doesn't make sense to me that Explorer can connect but net use cannot. That's the exact opposite of what I expect, where net use can always find the server even if it doesn't appear in Explorer.
Do you have access to the logs on the server? It would be worth checking smbd.log and nmbd.log to see if they record anything when you try to make the connection. Another possibility is to alter the debugging level to show more information. Have a look at this link
about troubleshooting Samba.