I have 7935's running with switchports (3550PWR) that have the following config:
switchport trunk encap dot1q
switchport trunk native vlan 1
switchport voice vlan 2
switchport mode trunk
spanning-tree portfast
They boot up just fine with DHCP, maybe it is a firmware issue? and if so I would imagine the newer 7936s would also behave just fine in a voice vlan config...