Looks like it's a DNS issue.Though it is not an Altiris issue from my first guess, I think I can help you with your DNS issue.
Did you get a ping response if you ping the FQDN. For proper NS Look up results in cross domains, you may need to add the DNS Suffixes for other domains here:
LAN Connection Properties.Internet Protocol (TCP/IP) Properties > Advanced TCP/Ip Settings . Add entries under Append these DNS Suffixes in Order. Look at the screenshot ( I added a test domain (LOL) fyr). So if you are in Asiapac and trying to nslookup a machine in EMEA, you need to add the entry for EMEA as mentioned below, assuming your DNS servers are set up properly.