We has a similar problem, only our setup was like this:
Phone A -> Callmanager -> Cisco ASA Firewall - > Callmanager -> Phone B.
In our case, the problem was that SIP inspection was only working in one direction. This is likely the case for you if:
You are using SIP trunks between CUCM and CME
You are using NAT between the two Callmanagers.
You need to have SIP inspeciton working properly on the IP2IPGW if you are using NAT, as NAT doesn't properly translate some stuff within SIP packets, but enabling and correctly configuring SIP inspection on IP2IPGW should do it (don't ask me how - should be plenty of documentation on it though).