I had this problem many times, not only using linux/samba but also in pure windows environment. Are you sure that dns server work correctly?
However the last time i have meet this problem, was when another samba machine in the lan had the same hostname of the domain...
To resolve these type of issue, usually i inspect the log of the server but also of the client machine (system events of windows xp).