Something is going on during the protocol negotiation stage that is causing the problem. If you let the connection try for some time you should get an error number and text that may shed some light. Can take several minutes.
I would suspect a problem with the IP address assignment. If you only have one or two client IPs established on the server for the connection, could be that they are not being properly released. If the connection is not terminated properly (sometimes even if it is), the IP address for the connection may not be released to be used by a new connection for quite some time. Sometimes even takes a day or two or a reboot. In this case increasing the pool of addresses available to the VPN server for the connection will help.
Similar problem can occur if you are obtaining the VPN IPs via DHCP and the DHCP server doesn't like something. If you are using DHCP for the addresses, try setting a static pool.
Also could be that your client is set to request an address, and that address is not being released properly. In this case, try removing the requested address from the client.
If none of those fit, next step would be to enable logging on the server side to check things out.