We've determined that there is a compatibility issue between our VPN software and the native Android 6 VPN client. We've implemented a workaround on our servers that will allow these clients to connect, however, this workaround may cause connection issues for other clients in the future so we may have to revert the setting if it is determined to be impacting other clients' ability to connect.
The problem lies in the Android client's implementation of the SHA2_256 hash. It was implemented using a draft version of the RFC which specified the hash should be truncated to 96 bits instead of the now standard 128 bits. This difference causes both ends of the tunnel to reject packets from the other end causing the tunnel to fail.
The issue has been reported to Google. Once they patch the issue we will disable the workaround to prevent future compatibility issues.