The biggest impediment to recording a todo item is that it is inconvenient. I use that excuse to tell myself, "oh, i'll write it down later". Later never comes.
The fewer clicks to the "add a task" prompt, the less likely I can give myself that excuse.
90% of time management is mental.
That's why I recommend paper (no boot-up time), and PDAs like the original Palm that make it very fast (minimal clicks) to write down an idea.
A related excuse happens when I'm in the NYC subway. With no internet connectivity (2G, 3G, or WiFi), any great idea I have on the subway is destined to be not recorded, and often forgotten, if the app I'm using requires the network.
What would be optimal? A "record a task" button right on the phone. You would press-and-hold the button, it would wake up and say "Recording". You would then say your task and use speech-to-text technology to transcribe the idea. If the speech-to-text server isn't reachable, it should hold the audio clip until it can be reached; possibly doing the translation in the background.
The on-screen or physical keyboard should be available too, of course, but what I really want is a super smart, voice activated, task recorder.
This is what Evernote does, at least on the iPhone. Text, voice and picture notes can be made while offline and they will sync once connectivity is available again.