I've been using Remember The Milk, because I need a To Do app that supports things like when this is complete, create the same task that is due again in 60 days, etc. RTM has an Android app which works, has notifications, etc.
I tried to use Astrid to link with RTM but it didn't work properly.