I've heard/read much debate on whether certain plants qualify as kitniyos, such as snow peas and quinoa. What exactly halachically defines "kitniyos?" is it based on what was popular in 13th century Eastern Europe, the biological definition of a legume, or something else?
Rabbi Moshe Feinstein writes that if a custom developed about it at whatever point in time, for whatever reason, it's kitniyos; if not, then not.
Regarding peanuts -- he doesn't say that they're not kitniyos because they're too new. He says there were different customs in different places, and where he came from had no custom against them. But if you know your ancestors developed the custom to treat peanuts as kitniyos, then they're treated as such.
Rav Moshe also suggests the possibility that at some point in time, rabbis ceased from adding more plants to the kitniyos list so there would still be enough things left to eat on Pesach!
The word kitnyios means legumes. However, it has come to mean any of a variety of foods from which different groups of Jews abstain on Pesach.
There is no set standard list of what is considered kitnyios, or even a set criteria of why foods might be considered kitnyios.
The gemara Pesachim 35a clearly states that only five foods can possibly become chametz: wheat, barley, oats, spelt, rye. Furthermore, it explicitly rules out rice and millet!
Yet rice, millet, beans, and other starchy, staple foods have been categorized as "kitnyios" by Ashkenazi communities for centuries.
When crops from the New World started to arrive in Europe, the kitnyios question renewed. Corn (maize) became kitnyios because of a linguistic error.
Blessedly, the potato escaped such scrutiny: however, the Chaye Adam wanted to consider potatoes as kitnyios as well
Foods that have only recently hit the Jewish scene, such as quinoa, are not considered kitnyios - although this plant has a slightly grain-like feel to it.
In summary, kitnyios has no specific definition. It is a custom. My personal feeling is, if such an illogical custom were to impinge our eating all year round, we would have done away with it by now. However, since it only applies for seven days (eight in the Diaspora), and it comes at a time of year when we are already significantly alerting our regular food habits, the ban of kitnyios on Pesach is here to stay.