People are too ready to leap at results that say, "Well, machines can never do X, and I can do X, therefore human-level AI is impossible."
In general, my counter to that would be "you probably can't do X either". It's just that you can do it well enough. You don't encounter the weird cases where your ability fails. But if that's allowed as an argument, then of course machines are more powerful too. I can absolutely solve the halting problem if "solve" can be interpreted as "almost always come up with the correct answer for the kinds of problems people encounter in the real world".
Also, don't forget what Terry Pratchett said, about how thousand-to-one odds crop up one time out of ten. The problems with AI in the past started when people tried to attempt to solve anything beyond the trivial, toy-problems they could demonstrate were solvable "in the lab". Like SHRDLU, which solved blocks world, but could not really scale. The same goes with machine learning today: some problems are solvable in restricted settings, or in a lab environment, under controlled conditions and with safe assumptions etc, but once you try to do the same thing in the wild...
You can even look at the big success of Deep nets for examples of that: image processing and speech recognition. Whereas it's possible to get really good results in both fields, image processing still relies very much on having good quality images to work with, and speech recognition is really crap if you have a bit of an accent, or a speech impediment etc. (at least that's what I gather- these are not my specialties).
Dana Angluin, Inductive inference of formal languages from positive data. [http://www-personal.umich.edu/~yinw/papers/Angluin80.pdf]
Dana Angluin, Learning regular sets from queries and counterexamples. [https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape...]
Mark E. Gold, Complexity of automaton identification from given data. [http://sebastian.doc.gold.ac.uk/papers/Language_Learning/gol...]
Mark E. Gold, Language Identification in the Limit.[http://web.mit.edu/6.863/www/spring2010/readings/gold67limit...]
Pitt, L., & Pitt, L. (1989). Inductive Inference, DFAs and Computational Complexity. 2ND INT. WORKSHOP ON ANALOGICAL AND INDUCTIVE INFERENCE (AII, 18--44. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.187....
Leonard Pitt & Manfred K. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86....]
Also see below for a gentle introduction to PAC-Learning, which actually allows for learning several concepts in restricted (but non-trivial) settings:
http://web.cs.iastate.edu/~honavar/pac.pdf
There is a lot more bibliography on both Inductive Inference tractability and PAC-Learnability. You'll have to follow the trail of references :)
Yes, it's entirely possible that we have missed something really important and when we figure that thing out we'll end up with a completely different Theory of Computation than we have now, and that may allow us to progress in learning concept classes that, today, are not learnable. That however, would be a revolution on par with Einstein's in physics.
Another thing that might save our collective ass, in terms of learnability, is that many of those results are assuming that P != NP. If that turns to be wrong, then those results will be off.
However, all this is very unlikely and in any case a) we can hardly expect such a profound re-interpretation of all that we know to happen within the next couple of generations and b) even if it does it remains the case that at this point in time everything we know suggests that there are some concept classes that we can simply not learn efficiently, at least not with computers.
Edit: what I'm really trying to say is that we may not understand human minds, but we're talking about computers here, so basically I agree with what you say, but with an added flourish :)
See deong's comment below. We may not understand how our minds work, but we do understand how computers work and that's where the learnability results come in: because they pertain to computers, not human minds.
Also, it may be that we don't need to learn every single thing we know. See Chomsky's Universal Grammar, etc.
Any result which predicts that human intelligence cannot exist.. has to have an error somewhere. Perhaps the error here is in assuming that a learning algorithm able to fit any function in polynomial time is needed in the first place.