Check FQDN is pinging for the right ip address
(Check is there any wrong host file entries , C:\windows\system32\drivers\etc\hosts , open in notepad )
Check for Remote Registry Service , Make sure its running in Source and target servers
---
There is one more common issue , running from Exchange 2010 to Exchange 2003
---
or
Try runnning from some other machine.
Satheshwaran Manoharan | Exchange 2003/2007/2010 | Blog:http://www.careexchange.in | Please mark it as an answer if it really helps you