samba - Nov 2005 - full path of samba machine from a different domain

I am not sure where to look into to resolve this. I have two domanins,
one is NT, another one is windows 2003 active directory. My samba
machine is in the active directory. Some of my users still in the NT
domain using the samba machine. Most of the time, they can access the
machine and authenticate via AD just fine using \\sambamachinename.
Lately, some of them are getting messages "network path not found".
Then if they type the fully qualified domain name, they get through.
Any idea?

--Sharif