Questions:
1) do you multiple PRI or just one?
2) does the problem happen consistently with certain DIDs or is it random?
3) is the gateway h.323 or MGCP?
4) is the gateway configured in the same CM location as the phone?
It almost sounds like the phones may be in a different location and your voice bandwidth is getting saturated. Please answer these questions and I will try to help you out.
Thanks.