We moved our branch traffic from a MPLS network to a VPN over the internet.

Everything is working except Messenger.

Local (Main Bank) users can connect, most users in the branches can not.

At least one user in each branch can connect.

The Messenger server is in the Main Bank. Ver. 2.0.1 Running on NW6.5 SP8

Those that can not connect get :

"The version of Messenger you are running is not compatible with the server
you are trying to connect to."

The Messenger Agent shows them hitting the server;
NEW PHYS. CONNECTION, Tbl Entry=17, Socket=98

They are using Messenger Client Ver. 2.0.1

No other changes. All gateway, IP Addresses ... stayed the same.

We have restarted the server, workstations, uninstalled and reinstalled the
client, pinged the server from the workstation, pinged the workstation from
the server, ran a tracert, ...