I have successfully connected to a PPTP VPN on Android. It is configured simply with an IP address, and no MPPE encrpytion. However, it does not show up under the Always-On option.
I am running Android 4.3 on a Nexus 4.
Setup DNS options for VPN connection. You may use any public-available DNS servers, for example 188.8.131.52
Note: Android 4.4+ have bug in the Always-On VPN feature: VPN stay connected, but all traffic is blocked because bug in system firewall. For fix this issue search AlwaysOnVpnFix application on Google Play.