The SDP offer from the gateway needs to include lines like this
a=rtpmap:101 telephone-event/8000
a=fmtp:101 0-16,36
The trace you collected should have the full SDP of the INVITE. If you don't have a line with 'telephone-event', that's why you are getting this error.
What kind of gateway are you using?