Usually, this is caused by mismatched switch type between telco and customer (e.g. telco is DMS-100, customer configured PRI NI2).
In CCM trace, you'll see something like:
08/31/2009 12:07:42.009 CCM|In Message -- PriSetupMsg -- Protocol= PriNi2Protocol
Check your CUCM and see if CUCM set to the same switch type. (device > trunk).
Hope this helps!
Michael
http://htluo.blogspot.com