NetBIOS name doesn't work when joining a workstation to domain

I've done a few searches in the past on this and have found the opposite of
the problem I'm having: When I attempt to join an XP SP2 workstation to our
domain using its NetBIOS name, the process times out and a message comes up.
Something to the effect of the domain cannot be located. If I use the FQDN
instead, the domain can be contacted and I get prompted for the credentials
to join the workstation. This is also a FQDN for a child domain:
child.parent.com Not sure if it makes a difference or not but I'm throwing
in as many details as possible.

If anyone has run into this problem and has found a solution or suggestions,
I would greatly appreciate it!

Thanks!

.