I use OpenVPN Server (with my WRT54GL router) and my Android Device(a Nexus One with CyanogenMod Nightly) connects correctly. The initial configuration was very hard for me (specially the certs) but i'm satisfied.

I have tried PPTP Server (simpler than Open VPN) but i avoid it because vulnerabilities.