Nelson spent a lot of time refining many ideas that were not really viable before the availability of computers. Given the timeframe (growing up under the shadow of the Military Industrial Complex and then maturing during the Cold War/proxy wars) he hit a very ripe time for populist activists.
I do think Nelson is one of the most influential thinkers regarding information science, but not as much as he desperately reminds people that he was. I also do not think his limitation is his inability to program computers, as he had a number of well-funded people helping at different times.
I suspect that, if you were to sit down and force rank the 50 most important thinkers of the 20th century, you'd have to exclude Nelson. Had he realized his ideas in a timely fashion, or inspired anyone to realize and exceed his visions, then his place would be secured.
However, I think much of what he created, other than the specifics of a great potential implementation, would be classified as simultaneous invention. Semantic networks existed before hypertext and it's a pretty nominal step from there to the basics of hypermedia. The Mother of All Demos is probably the best example of his contemporaries realizing their ideas.
What he does have is charisma and an ability to communicate his ideas. He gets people fired up about his dreams of a better world, and yet it has not come to pass. No one has been inspired enough to implement Xanadu. It's appropriately named. It's an interrupted dream that is incomplete.
Nelson's writings have a different sensibility from the mainstream of both his fellow computing pioneers of the 1970s and the hackers of today. An example of his thinking from before even UNIX was a household name is that Nelson decried hierarchy as a form of organization for data (e.g., in a computer's file system), instead emphasizing association [2], which he thought closer to how humans actually organize knowledge. He also argued that instead of dialogue-based computer instruction that was taking off at the time the best method to use a computer for learning would be to "motivate the user and let him loose in a wonderful place", that place being a hypertext knowledge base (see [1], p. 313).
It is disappointing that in spite of Nelson's books being incredibly influential (to the point where they were reprinted by Microsoft Press because of the company's fondness for the author) most of his ideas never saw a complete implementation in a popular product. I'd love to read a doctoral thesis/book on the history of Project Xanadu -- a hypertext Web project started in 1960 that was supposed to have content transclusion and microtransactions (!) -- with an in-depth analysis of the factors that led it to where it is now (i.e., still unfinished today). (Gary Wolf's article "The Curse of Xanadu" [3] is the closest we have to that but it has multiple problems, to the point where Nelson has published a refutation [4].)
Today Ted Nelson's background in art (the man has, among other things, a claim to writing the world's first rock musical [5]) and fondness for pure performance (which is what I believe his recent video "I Think I Know Who Satoshi Is" [6] to be) may be a factor that limits the appeal of his message to most "techies" (his term), preventing them from more deeply investigating his message.
[1] http://www.newmediareader.com/book_samples/nmr-21-nelson.pdf
[2] Nelson's alternative to the file hierarchy was associative "metadata" a-la the MEMEX (https://en.wikipedia.org/wiki/MEMEX#Associative_trails). With WinFS canned I'm still waiting for someone to implement something even close to that.
[3] http://www.wired.com/wired/archive/3.06/xanadu.html
[4] http://xanadu.com.au/ararat
[5] http://people.oii.ox.ac.uk/dutton/2007/12/10/the-first-rock-...
[6] https://www.youtube.com/watch?v=emDJTGTrEm0