There are currently no logon servers available to service the logon request

Solution 1:

Your wording suggests that perhaps those users have never logged on to those laptops while the laptops were connected to the network. In such a case their credentials have not yet been cached. The laptops must be able to communicate with the domain controller for at least one login per account.

Solution 2:

Have a look to see if you can't launch the VPN tunnel before user login, that would be the best solution.

Also doublecheck DNS settings: is the default DNS server the same as (or trusted by) the login/domain server?

And what OS version is running on the login/domain server?