There are well known classes of problems that are intractably difficult for computers, and other classes that are provably undecidable. Does this mean that AI is impossible?

These problems are only momentarily undecidable. As comes with more advanced technology, there will be more intelligent artificial intelligence. Besides that, artificial intelligence doesn't need to be able to solve these quandaries to prove itself real.