I had to completely reboot my system a couple of years ago and used paper as my starting point... and am still using it now! I have found that keeping things simple works well, particularly when you are rekindling the GTD basics:
- 2 minute rule
- What is it? What's the next action?
I also found that labelling my old stuff as backlog and working from a clean sheet really helped me to get back on top of things. I then tried to make time to deal with the backlog items systematically.
Good luck and let us know how you get on!