I've found Toodledo (http://www.toodledo.com/) to be the only cross-platform service that supports Getting Things Done (GTD) well. It leaves some things to be desired, but I haven't seen anything else out there that both

1) Supports a GTD workflow

2) Works on both iOS and Android (but also has a web interface).

Toodledo syncs well with apps like 2Do (available for both iOS and Android) and Pocket Informant.

If you (or anybody else) is interested in migrating to Toodledo, I wrote a Ruby client library for the Toodledo API that may be handy - ping me and I can send you the link.

And if anybody has other suggestions for services that fit both of the above requirements, I'd love to know.