Hi Mary,
I see no one else has answered so I'll give it a go at helping.
It sounds to be as if you're having issues with the Call Setup signalling getting through to or from the gateway itself.
You often get this sort of thing if there's network issues - is the gateway local to the CallManager: can you continually ping with gateway IP address from the CM without problems?
The other thing to try is to check the Event Logs on the CallManager. If you're having issues with call setup often the System or Application logs will report an issue with some of the services. Give it a go and see.
Hope this is of some help.
Cheers,
Stu