Well, one thing you can try is Virtualbox's built-in proxy tool. VirtualBox-->File-->Preferences-->Proxy. I've never used it before, and I'm not sure how it'd effect Genymotion, but it's worth a try.
As for Android Proxy apps, you'll just have to try several different ones from the Play Store until you find one that works, if any. A possible reason the Proxy apps are getting messed up is because Genymotion VMs actually use two Network connections. The first one is for Genymotion's software to talk directly to the VM, and the other is used for the normal internet connection.