I was frying onions and garlic the other day and the paste turned green. I had bought the onions/garlics many days ago (20-30 days) I guess. Could that be the reason? There was no fungi or something suspicious when I cut them by the way.
I've also had this happen when cooking an onion-garlic paste. I've found several web pages where the phenomenon is discussed, listed below. In summary, it's normal and happens due to certain chemical reactions between the garlic, cooking utensils and water. In your case, it's probably not due to the age of your garlic or onions though, as one source suggests it is less likely to occur with aged garlic. I've only seen the paste turn green myself, though interestingly you could also get blue garlic:
Garlic contains sulfur compounds which can react with copper to form copper sulfate, a blue or blue-green compound. The amount of copper needed for this reaction is very small and is frequently found in normal water supplies.
Garlic Can Turn Blue
Raw garlic contains an enzyme that if not inactivated by heating reacts with trace amounts of sulfur (in the garlic) and copper (from water or utensils) to form blue copper sulfate. The garlic is still safe to eat.
Garlic can turn Green
If the garlic was not fully mature or dry, pigments in the garlic may turn green when in the presence of acid. Garlic will also turn green (develop chlorophyll) if exposed to an temperature change or is exposed to sunlight. Some people say it can be stored for 32 days at or above 70 - 80° F to prevent greening, but I'm not yet sure that is true. Green garlic is safe to eat.
Some other pages where this is discussed: http://chowhound.chow.com/topics/471608, http://www.cheftalk.com/forum/thread/45254/onions-turned-green-while-frying, http://whatscookingamerica.net/Q-A/bluegarlic.htm.