What's the evidence that the colors were added later?

[Jorge_Stolfi]

It is often said on this website that the painter had no clue what he was doing and was using totally random colors.

Not entirely random.  In the herbal section, he would normally use green for at least half of the leaves, brown for the roots, and other colors for the flowers.  He (or they?) used light yellow for the sun and nymph's hair, red for their lips, red sprinkles for their cheeks, blue or green for water flows, showers and pools, blue for starry skies...

But for me the case of Gemini shows that sometimes he knew what he was doing:
There is apparently some line of tradition that in Gemini man is green and woman is blue and he follows this tradition.

Good eye spotting that.  But surely the Painter must have been influenced the tradition of his place and times.  Like the original Scribe was, when he drew the nymphs' hairdos, hats, and dresses, the sun with wavy rays, used a nebuly line for the boundary of the sky on f68v3, drew dragons(?) next to some roots, drew castles with Ghibelline merlons, etc.

Whatever the origin of the VMS, by 1600 it was in Prague.  We can guess that, for some part of the previous 200 years, it was somewhere in Central Europe, in the area of "German" culture.  I suppose that the painting occurred in that time span, or at most before Marci sent it to Kircher.  I can't imagine it happening after it was in the Jesuits' hands.  

The VMS may well have been traded before it got to Barschius.  Then the painting may have been done in order to made it easier to sell and/or increase it price -- since it seems that people at the time expected herbals to be colored. 

All the best, --stolfi