We had the exact problem when we installed our system. We found that IOS 12.2(2)T is the only IOS version that worked for us on the Gateway.
The codec for the Gateway must be set to G711ulaw in the dial peer :-
dial-peer voice 500 voip
destination-pattern 5..
progress_ind setup enable 3
session target ipv4:10.1.0.2
dtmf-relay h245-alphanumeric
codec g711ulaw <---"Strange because I am in the UK"
Although if you use softphone remotely you will need to use this config :-
voice class codec 1
codec preference 1 g711ulaw
codec preference 2 g729r8
!
!
dial-peer voice 500 voip
destination-pattern 5..
progress_ind setup enable 3
voice-class codec 1
session target ipv4:10.1.0.2
dtmf-relay h245-alphanumeric
This will allow softphone to connect with the "always use low bandwidth codec" set.