OmniFocus? I think it is a great software but making two big changes at once is very, very difficult. By two changes I mean learning and implementing GTD and OmniFocus. That is why I always advise to use the tool you are proficient with at the beginning (for most people it is a paper).
Just a thought on this: Paper is indeed probably more natural for most people. But at least for me, someone who's used the computer at work and home to the almost complete exclusion of paper (except for reading books) for years, it's the use of paper that would be the new skill to learn. ("It takes _how long_ to write those six words? I have to _erase_? If i use a pen there will be visible errors on the page? Oh, my God!") I didn't experience OmniFocus as a second barrier, but instead as a bridge easing my path to the GTD practices.