Found a solution :0)
I had the same problem. You are using TCP. Even if you setup the trunk to use TCP and UDP, you still need to enable tcp globally. I am using freepbx to do this, so here is what I did.
First SSH to the box and modify /etc/asterisk/sip_custom.conf to put the global parameter.
tcpenable=yes
transport=tcp
Then I created the trunk. Trunk information shown below:
Trunk name: lync-nac-trunk
Outgoing settings:
Trunk Name: lynctunk
PEER Details:
host=10.56.100.16
type=friend
transport=tcp,udp
port=5068
dtmfmode=rfc2833
qualify=yes
tcpenable=yes
transport=tcp
Then save it.
Now see if the trunk is registered.