AI has a long history of encountering mathematical impossibilities and then working around them already. While the individuals who solved these problems don't get as much press as Newton, Einstein, or Hawking, a case could be made that their contributions to human knowledge are on a similar scale. Unfortunately, their results don't relate to physical systems, so they can be harder to explain to the layperson.
Something to keep in mind is that your question assumes the correctness of the "Great Man Theory" of science history, which holds that science advances by the efforts of exceptional people, and that we need to wait around for more such people to appear for science to advance. This view of scientific history is overly simplistic, and probably wrong. For example, most (all?) of Newton's discoveries were likely to have been made by someone else, around the same time, if he didn't make them (see, e.g. Leibnitz, who actually did discover calculus at the same time), so a better view might be of a large community of researchers who gradually develop more advanced models based on each others' work.
To answer your question, I've listed out some past examples of problems that were overcome, and some outstanding problems that might require the development of new mathematical tools to solve properly. Keep in mind though, that we can't know for sure whether new tools are needed: maybe existing tools are sufficient, but no one has applied them in the right way yet!
Some past problems that plagued AI and required the development of better mathematical approaches:
The combinatorial explosion problem appeared to preclude having an AI system reason about probabilities and causation in a logically correct way. This problem was solved by the development of Bayesian networks and causal networks, with the work being led by Judea Pearl and his students. Pearl won a Turing award for this, but has received very little coverage in the popular press.
Many optimization problems that AI systems need to solve are NP-hard. This means that no general purpose algorithms exist that can give exact solutions to these problems in a polynomial number of steps. Because of this, the problems were initially viewed as intractable. The development of PTAS algorithms, and a deep understanding of phase-changes in NP-Hard problems (pioneered by Cheeseman et al.) led to an ability to identify exactly what makes these problems hard, to identify which subparts cause the hardness, and to practical algorithms that solve all sorts of problems in these domains.
Much effort in AI was spent designing new classification methods, and arguing about why one might or might not be better than another. The No Free Lunch Theorems, along with other work in computational learning theory provided a clear mathematical framework for understanding how systems can learn, and where their limits are.
As a more recent example, games involving chance, like Poker, have state spaces so vast that they cannot be searched through effectively, even with heuristics. Phrasing these games in the language of Game Theory, and proving the convergence of the counter-factual minimax regret algorithm provided solutions. Bowling et al. were at the center of this work. It got some press coverage, but most of the coverage focused on "computers can play poker", and not the exiting, more generalizable, lessons AI researchers had learned in the process.
Some problems that are still outstanding, and might require new mathematical techniques:
Are there efficient algorithms for solving problems in the complexity classes PPAD, NP, or #P? Many AI problems fall into these categories. We do not know the answer definitively, and although most researchers suspect that no such algorithms exist, understanding why not seems like it could also provide major research advantages. Existing proof techniques do not seem likely to crack this problem.
We have no good mathematical models of subjective experience. While some researchers (like Churchland) think this is not likely to play a major role in the development of intelligent systems, a concrete model could either support or refute that view, and might provide solid frameworks for current problems in AI like the study of motivation.
The original project of the social sciences was to provide mathematical models of individual humans, and then of human societies. This has mostly been abandoned (Psych is still at it, but Economics prefers to study rational agents instead of humans, and most of the others gave up mathematical modeling entirely to pursue the methodologies of the humanities instead of the sciences). Nonetheless, the lack of sound mathematical descriptions of human behaviours is becoming a major topic within AI, with work on norms, trust, emotion, and other topics. If a mathematical framework were developed to describe the actions of human societies or of individual humans, then AI would be advanced significantly (along with many other fields!).