Let's start with the good news, I use an android behind a DFL every day, and have never had an issue, so our problems won't be insurmountable.
If you correctly set an any/all-nets/all-services rule, then we can probably factor out IP rules. unfortunately, I suspect that this will be a HTTP ALG issue, and so we need to be doubly sure that your allow all rule was number one on the IP Rules list.
Do you get any log entries when the traffic fails?