Cannot Access W2K shares from Win95/98

When trying access a shared drive on a W2K workstation through Network Neigborhood on a Win95/98 machine, I get the following error message.

\\devicename is not accessable.
This device does not exist on the network.

The 95/98 machine is set up to log onto the domain. The logon is also setup as a local user on the W2K workstation with administrator rights.

W2K to W2K shares fine.