Definitely sounds like a carrier issue... I would want to see EDT L2L3 traces of a failed call to see where the issue lies, the command is:
EDT TRACE TSP L2L3 <PLID of PRI> (Note this is a toggle, issue it once to start the trace, again to stop the trace)
If the system has a fair amount of traffic this can be very lengthy quickly and difficult to diagnose, but it should give you the information you need to see where and possibly why the call is not completing or disconnecting.