It sounds like H245 negotiation is not occurring. Does Avaya want to see fast start or slow start media neogitation?
Run 'debug h225 ans1' 'debug h245 asn1' and 'debug ip tcp trans'. At the connect there should be an h245 address, and a TCP link should open up to exchange media negotiation (MSD, MSDA, TCS, OLC, OLCA, etc.).
Make sure that the H323 gateway instance on CUCM has 'wait for far end h.245' unchecked, too.