The problem is the value contrast between the light green and some of the similar shades of white, light blue, and gray in the painting. For instance, if you changed it all to grayscale, some of the letters would hardly show up.
If you darken the green, you'll just be shifting the problem to other parts, and lightening will do the same.
To get more readablility, I recommend making the letters cast a "knockout" shadow onto the painting. The result is that it looks like you have a green surface with the letters cut out of it revealing the painting jsut behind it.
In Photoshop, knockout drop shadow is a layer effect, I believe.