It seems that the CODEC negotiation is actually completed, and G.729 is chosen:
v=0
o=CiscoSystemsSIP-GW-UserAgent 3428 9294 IN IP4 10.198.129.46
s=SIP Call
c=IN IP4 10.198.129.46
t=0 0
m=audio 17290 RTP/AVP 18
c=IN IP4 10.198.129.46
a=rtpmap:18 G729/8000
a=fmtp:18 annexb=yes
a=ptime:20
That, in fact, may be the problem. Most scenarios with SIP Trunks on the CM require G.711.