I have it working on my VPN'd network, but my setup is a bit different. I have a BSD router that creates the VPN connection between two networks. Then on a Linux server, I run mdns-repeater which rebroadcasts mDNS packets across two interfaces. The caveat is that whatever computer running mdns-repeater must have access to both connections.
In the case of VPN on a single device, it's a bit more difficult because most VPN implementations will not forward broadcast/mDNS packets across the links. I'm using OpenVPN which allows complete bridging (as if the VPN connection was ethernet). As far as I could tell, PPTP and L2TP do not allow this. So I haven't yet gotten the App working via the built-in iOS VPN connection. If you can run OpenVPN w/ Bridging on Android, that should work.
Ideally, if your VPN server is also capable of running mdns-repeater, you might be able to force the mDNS packets down the VPN tunnel, but I haven't been able to get that to work with PPTP yet.