If you assume this has something to do with changing Telcos, debugs those calls, if you see them coming back into your system, then you might need to get in touch with telco.
If you don't see anything in the debugs, and those calls don't even make it to the GW, then the problem has nothing to do with your telcos, and it's caused by your own CUCM config. You would need to fix whatever routing problem you have.
HTH
java
if this helps, please rate