Thanks heaps PeterW. I have already got an account with NirvanaHQ and am awaiting the release of their Android client. Here's hoping.
If they only knew that I would pay for it like yesterday!
BTW, does OmniFocus do this? I've been thinking of finally biting the bullet and getting a Mac (for various reasons) and if so I'd have to start this whole search over again. I know Life Balance is what MLO was originally modeled on, but I'm not sure whether that will run on newer versions of OSX.
A Linux option would be interesting as well.