That sounds like a keep-alive issue. What protocol are you using to talk to the Cisco gateway? H323, MGCP, or SIP? Also, what codec are using, G. 711 or G. 729?
If this is a H323 gateway, most likely the issue is something to do with the H. 225 portion of the H. 323 protocol. The H. 225 portion of the protocol handles the call control portion. So I would recommend running at H. 225 debug on the gateway.
debug h225 events
Using this debug command, you will see the Q. 931 protocol messages going between the two gateways and this may provide you with a clue on what your issue is. Also remember on Cisco voice over IP gateways you should check the Cisco web site for any bug related issues with the IOS code you are running on your gateway. There gateway can support it I recommend running at least 12.2.13T code or better for the best performance. Cisco’s 12.2.13T code introduces some new features such as enhanced echo cancellation and echo suppression.
Another two things that would check is make sure your codec negotiation is correct and your IP routing is configured correctly. A lot of voice-over-IP issues starts as simple data connectivity issues. The majority of one way or no way voice issues are a result of simple connectivity problems.