Couple of things.
1. Are you using hardware or software conference bridge? If software, make sure the Region setup is such that the call leg between the gateway and the Conference bridge uses G.711 codec. If it is using G.729, then make sure you have transcoding resources available.
2. In the Callmanager gateway configuration, make sure the Media Termination Point Required is unchecked.
Regards,
Anup