If you're pinging ok and the traceroute looks good then it would appear that your network is ok.
Generally, I see this when the IP address isn't right or perhaps the programming for the remote PBX is wrong.
If you've gone through all of that and you know nothing has changed then you may want to try the simple thing - reboot both controllers.
Usually though, it's a programming issue.
Are these systems on the same subnet?
Do they traverse a firewall?
Ralph