Ye Olde List o' Annoyances:
#1: I could only view one list at a time. I like having a 'big picture' view. Plus, the default-in-Gmail view was tiny. I could pop it out, but then it was in an orphan browser window -- which would sometimes disappear because it still technically tied into Gmail (e.g. adding a Labs extension to Gmail made Tasks go poof).
#2: They positioned the delete button between the "Add Task" and "Switch List" buttons. I nuked a few tasks accidentally, without evening know what I deleted.
#3: There's no undo and no history. If I wanted to hide completed tasks, I had to delete them, which meant losing them forever. If I accidentally deleted a task thanks to the positioning of the delete button, well, too bad.
#4: I couldn't select multiple tasks and move them around.
I couldn't take the annoyances.
I've since switched to a homebrew todolist solution that lets me see everything at once, switch between contexts, edit multiple items at once, and keep a full history. I complement this with a Moleskine notebook as a collection input. For stuff that has a hard due date, I use Google Calendar.
As for paper vs. iPhone -- I don't have an iPhone so I'm quite happy with paper. My notebook fits comfortably in my pocket and goes with me everywhere, and Moleskine thought through the design so its pages don't wrinkle and it stays nice and neat while remaining easy to write in. I've only used it for two weeks, but I've found it well worth its price compared to el cheapo pocket notebooks (which I used for several months, until I gave up in frustrating at having them wrinkle after living in my pocket).