do these inter-tel phones not use 802.1q?
if they do as i expect from what i hear, i would suggest using a sniffer to capture some of the traffic from the phone and see if you can determine why the packets are not being marked.
if you see an 802.3 frame with no 2 byte 802.1q 'tag' field, then perhaps there is a problem with the inter-tel marking or not configured correctly.
if you do see the inter-tel phone marking correctly with dot1q, then perhaps the catalyst has a misconfiguration. (you're using 802.1q not ISL for the trunk right?)
is the vlan of the phone, as configured on the catalyst, the NATIVE vlan for the trunk? if so, this could be your problem as a NATIVE 802.3 frame will not be required to carry an 802.1q tag.
please provide catalyst configuration if possible and how the inter-tel is configured if possible so we can see more and help more.