This has been a fun topic of discussion on Server Fault. There appear to be varying "religious views" on the topic.
I agree with Microsoft's recommendation: Use a sub-domain of the company's already-registered Internet domain name.
So, if you own foo.com, use ad.foo.com or some such.
The most vile thing, as I see it, is using the registered Internet domain name, verbatim, for the Active Directory domain name. This causes you to be forced to manually copy records from the Internet DNS (like www) into the Active Directory DNS zone to allow "external" names to resolve. I've seen utterly silly things like IIS installed on every DC in an organization running a web site that does a redirect such that someone entering foo.com into their browser would be redirected to www.foo.com by these IIS installations. Utter silliness!
Using the Internet domain name gains you no advantages, but creates "make work" every time you change the IP addresses that external host names refer to. (Try using geographically load-balanced DNS for the external hosts and integrating that with such a "split DNS" situation, too! Gee-- that would be fun...)
Using such a subdomain has no effect on things like Exchange email delivery or User Principal Name (UPN) suffixes, BTW. (I often see those both cited as excuses for using the Internet domain name as the AD domain name.)
I also see the excuse "lots of big companies do it". Large companies can make boneheaded decisions as easily (if not moreso) than small companies. I don't buy that just because a large company makes a bad decision that somehow causes it to be a good decision.
Best Answer
It sounds like DNS resolution. If it's on the same subnet then it cannot be the firewall.
Can you ping this machine by both hostname and fully qualified domain name in both directions?
Well, if they are both using the same DNS server and that server is responding to the queries that is a good sign that the problem is not so severe.
If the machine cannot ping and you mentioned they are on the same subnet, check for an IP addreess conflict as well as check that there are no typos in the subnet, gateway, netmask, etc...