I was paid (a very small sum) to consult Nicholas Ostler on this issue --and I'm thanked for it (briefly) in his book _Last Lingua Franca_.
This does not mean that I endorse the views about Pali stated in that book; however, this was very much one of the points of confusion that I tried (at length) to educate him about --and he did revise his manuscript to reflect what I had explained to him (to a limited extent). However, he did not want to let go of the notion that is written on the front cover of his book, i.e., that Pali was "a Lingua Franca", so he opens and closes with this bias.
I differ from the explanations offered by Kare in several important respects (but I do see that he is making a worthwhile contribution, that is probably educational to many people on this forum).
A few clarifications are necessary.
(1) Pali was always in the class of "artificial languages".
This means that Pali was always different from the natural language spoken within the household (and in the marketplace) by common people --AT LEAST to the same extent that Shakespeare's English was different from naturally spoken English in the households (and marketplaces) of England during Shakespeare's life.
That's a limited comparison, but a useful one: for much of the history of the English language, there has been a contrast between "theatrical English" and the commonly-spoken language (not today!) --and we still have a contrast between "legal English" (almost an artificial language) and the commonly-spoken language.
(2) The Pali language was defined by the creation of the Pali canon: it emerged out of a cultural context in which various Prakrits were used (as artifical, written languages) to various purposes. This was not unique in this era of India's history: we have a stunning parallel in the emergence of Jain Prakrit, as the Jain religion codified its earliest (extant) holy texts during exactly the same period of time.
Jain Prakrit and Pali (qua Buddhist Prakrit) are different languages, but they are similar enough to match exactly this description: they both emerged from a cultural context in which various Prakrits were used to various purposes, and the vast majority of words share etymologies (i.e., where spellings differ, they often have, nevertheless, a common underlying form).
(3) Kare is correct that Magadha is very nearly a red herring: many, many different languages were spoken there, and it is likely that the Buddha himself communicated in more than one language, if he did walk over the geographic span described in the canon, and did speak to many different ethnic groups, caste groups, etc., as described in the canon.
The recording of what the Buddha had said in Pali would have been an artificial process, in the same sense that writing a description in poetry is artificial --and in the same sense that we "translate" events into legalese. The various monks involved in that process would have been familiar with one Prakritic tradition or another, and the imposition of uniform spellings on the results resulted in a distinctive Prakrit for Buddhism --just as (simultaneously!) the same region was home to the emergence of a distinctive Prakrit for Jainism.
(4) The extent to which anyone involved with that earliest chapter of composing poetry and prose in Pali (and rendering informal speech in to the very artificial style of discourses in the canon) was influenced by Sanskrit (rather than Prakrit) would relate very strongly to the caste identity of the persons involved. Everyone now supposes that significant numbers of the first Buddhists converted from Brahmin Hinduism, and were familiar with Vedic written tradition, etc., and, likewise, there were converts from the Jain tradition, etc. --along with myriad other religious traditions that have no extant evidence (that they ever existed) aside from their echoes within the pages of the Pali canon.
So, yes, the composition of the Pali Canon has more Sanskrit influence than (e.g.) Munda influence (although you can find a few Munda etymologies in there!) --but we are basically talking about a tradition that emerged from the lively Prakritic language context of its day (something that is difficult for modern people to imagine).
(5) So... what language did the Buddha speak? Well, within the geographic area that he (reportedly) came from, the main evidence to consider would be his presumed ethnicity. Is anyone willing to really look at what the ancient texts say about his ethnicity? In my experience, the answer is no:
That article discusses several aspects of the Buddha's reported physical appearance, from baldness to blackness, and the cultural perception of him within ancient India. In terms of the Buddha's "mother tongue", you can look at his ethnicity, and the small town (and small tribe) he was supposed to come from, and draw up your own "best guess" based on the historical evidence.