The normal linux pptpd will talk to the normal Android PPTP client, but brokenly by default. The magic configuration change:
/etc/pptpd.conf refers to an option file, in my case /etc/ppp/pptpd-options, which can be used to send the VPN client various information, such as which DNS servers to use. You have to set that option, or the Android phone silently fails. You then cannot open any web pages, or do (almost) anything else, because all DNS lookups fail on the Android phone.
The fix is to send the Android phone the ms-dns option:
$ grep '^option ' /etc/pptpd.conf
$ grep '^ms-dns ' /etc/ppp/pptpd-options