With out specifics....cant help much

What routers..are you, and the other companies using....firewalls...OSes

Could be a limitation of the router and the amount of simultaneous VPN connections it allows??

MLF