I was using first Tasque and then GTG on Ubuntu and Astrid on Android with Remember The Milk as the backend. Recently, Astrid has dropped support for Remember The Milk, and both Tasque and GTG's support for syncing with RTM has always left something to be desired. So I'm looking for a new solution, and I'm open to leaving RTM especially if it is for something that isn't proprietary.
What have you found to keep your tasks lists in-sync between Ubuntu and Android?
In particular, I'm looking for a desktop based program on the Ubuntu side rather than something in the browser. Astrid has treated me well, but I wouldn't mind trying something else. Currently, it can sync with Astrid.com, Google Tasks, and Producteev. Anyone know of a desktop app that supports any of those?