I use Nozbe which provides an in-browser app, iOS, Android, Mac and Windows apps. No Linux app but you're covered with the in-browser app. I find it to be extremely robust in terms of syncing and in general having a smooth, fast, error-free "task capture," which is like 90% of what I need out of a GTD product. From that point you can organize tasks by either project or context. It also has really nice syncing with Evernote and with Google Calender which I use extensively, and also integration with Twitter and all kinds of other things which I don't use.

In terms of what doesn't work, I've written elsewhere about how Emacs org-mode is superficially the Best Thing Evar but is actually an infinite timesink that will actually just eat all your tasks. You think you want total customizability but what you actually want is structure and the freedom from having to think.