VPN Error 778: It was not possible to verify the identity of the server

We have a Windows 2003 server with Routing and Remote Access configured to support PPTP VPN. We recently migrated the server infrastructure to a new location, although all public and private IP addresses remained the same. Since the move, clients attempting to VPN using the native VPN client in XP, Vista, or Windows 7 receive this error most (but not all) of the time:

Error 778: It was not possible to verify the identity of the server

Connecting from a client network that is only one hop removed from the hosting network works consistently.

I set up a different Windows 2003 server on the same network with the same VPN configuration, in case the problem was with the server configuration. I get the same results.

My Apple iPad device consistently connects regardless of the server. Presumably this error is coming from a security check done by the Windows clients that the iPad skips.

UPDATE: if users leave the password field blank on the Windows VPN client and then enter their password into the "incorrect password" prompt, the VPN connection consistently completes. This must cause something different must occur in the handshake process.