In the below hadith the Sahabi said a new Duaa in the prayer and the Prophet welcomed that, Isn't this an innovation? if not, please explain me what is bid'ah (Innovation)?
Bukhari :: Book 1 :: Volume 12 :: Hadith 764
Narrated Rifa'a bin Rafi AzZuraqi:
One day we were praying behind the Prophet. When he raised his head from bowing, he said, "Sami'a-l-lahu Liman hamida." A man behind him said, "Rabbana walaka-l hamd hamdan Kathiran taiyiban mubarakan fihi" (O our Lord! All the praises are for You, many good and blessed praises). When the Prophet completed the prayer, he asked, "Who has said these words?" The man replied, "I." The Prophet said, "I saw over thirty angels competing to write it first." Prophet rose (from bowing) and stood straight till all the vertebrae of his spinal column came to a natural position.

First we have to clarify the meaning of bid'ah:
The Prophet (peace and blessings be upon him) said: "He who introduces something that is not in agreement with our matter (religion), will have it rejected" [Bukhari).
The Prophet's words illustrate that acts initiated in Islam that do not conflict with the established principles of Sacred law are accepted. This was exactly what 'Uthman ibn 'Affan (may Allah be pleased with him) did when he introduced the second Adhan [Eng. call to prayer] before Friday Prayers. And this is how the imams and scholars of the followed schools of jurisprudence understood the concept of bid'ah.
If we do not follow this opinion, life will be hard on people and they will have to abandon many matters concerning their livelihood.
Categories of Bid'ah
Scholars classify bid'ah into five categories: Permissible, recommended, prohibited, offensive and obligatory i.e. it takes the five rulings of obligation.
However, some scholars deviated from this opinion and claimed that every bid'ah is an evil. In this manner they contradict the words of the Prophet (peace and blessings be upon him): "Whoever initiates a good Sunnah in Islam, earns the reward of it and of all who perform it after him until the Day of Judgment and whoever initiates a bad Sunnah in Islam, will bear its sin and of all who perform it after him until the Day of Judgment". This is the established opinion of the Muslims from the predecessors and successors without any denial that can be taken into account.