Mind if I go a little off-topic here? This paradox reminds me of some other conclusion I've had, which is the fact that energy requirements of many physical processes are completely counterintuitive. For instance, it probably takes more energy to light a light bulb for a day, than it takes a small processor to run a set of calculations equivalent to a lifetime's worth of arithmetic done by every human being alive today.
>Kind of renders all of his information theoretic calculations moot.
The stuff in the article isn't information theory. Information theory, in the senses of Shannon and Chaitin, is actually very useful for studying cognition, because it tells us about how much we can try to learn, via what methods, from noisy sensory data.
Moravec's paradox is not an experimental result. It's just one guys musings on intelligence. It says a lot more about the misguided things people thought about intelligence in the early days of AI than the actual inherent difficulty of achieving human-level AI.
According to the linked article, several notable researchers were of the same opinion (and one might also say that relativity was just one guy's musings - though admittedly experimental evidence wasn't long in coming.)
I do, however, agree with your second sentence, and I think the paradox is also weakened by the fact that when 'high-level' mental tasks are computerized (chess-playing, for example), it is often through brute-force calculation that is not a model of how humans use their general intelligence to perform the task.