Windows Messenger 5.1 - LAN-to-LAN clients failed...

Greetings.

I have this situation: My whole network is using Lie Communications Server 2005 and Messenger 5.1.
All clients work fine, except the ones using an IPSec LAN-to-LAN tunnel. Those guys connect to server, but when someone adds them to their contacts, and they try to reply "Yes, add them also to my contacts", an error stating that the Service cannot be contacted appears.

Using "netstat -n" command, I verified that the port 5060 is being used, so....
Is there any thing I may be doing wrong ?

Thanks to all in advance !