I've been on the GTD trail for 15 years, with varying degrees of success - ironically, my highest degree of success was in the mid 90's with the Time Design system. Software does promote complexity because it has more functionality. A paper list does nothing but hold written notes. It encourages simplicity.
From personal experience and this forum have convinced me that most of the complexity with which people struggle, on paper or on software, comes from trying to do Project Management within the GTD system. That doesn't work. PM is very complex and requires a lot more resources than lists of next actions. It requires precedence relationships and critical path analysis. GTD helps do projects, but the emphasis is on atomic actions, not the big picture. GTD provides lists of NA's organized by context and readily available and current, but there is no inherent relationship between lists, or actions, in a GTD system.
At the GTD seminar I attended people kept pushing DA for PALM software recommendations to manage this and that (usually PM type activities). DA help firm. He uses PALM straight out of the box; NA list, contacts, calendar and notes. The goal is to keep you focused on executing NAs and to avoid distractions of with maintaining the system.
I could be completely wrong, of course. I currently struggling to get back into GTD after a 2+ year absence. Feel free to suggest corrections.