I just did a lab where the scenario was vlan information was not being propagated over a trunk link (only 2 switches in this lab).
After checking the obvious (eg trunk is operational, matching vtp domain names, etc.), it turned out that you had to issue a "no shut" command for the native vlan (using 802.1q, native vlan 1).
It seems the native vlan has some association with trunking. What exactly is the connection?