We used to be able to connect to NetWare server on the NW6.5 SP5 network
from a workstation using Windows' Start | Run and typing the UNC to the
resource (e.g. \\SERVER\VOLUME). However, within the past few months and
using various client versions (4.91 w/ various SPs) we are unable to
connect to the resource as aforementioned. I am logging in as an admin
user to a server that holds the [Root] replica.

We can connect using the DNS name (e.g. \\SERVER.DOMAIN.COM), and we can
then subsequently connect to that resource using the UNC path
\\SERVER\VOLUME; makes sense because we've made the connection, so
there's no need to search for the server name again...

Not sure if this is client-specific, SLP, etc. Can you give me some
troubleshooting ideas?