Ok, first let me make sure that I understand you correctly. You have:
-A pure red cube.
-A greenish ambient light.
-One or more various other lights.
-You are wondering why the shaded side of the cube (lit only with ambient) renders as black.
If I got it right, keep reading. If not, please explain where I went wrong.
What is happening here is that your red material cannot reflect green/blue light, so the cube appears black. You can see the same effect in real life. Take a green LED and a red apple into a dark room. The apple will appear black.
Of course, 'pure' colors are rare in real life. (a laser beam and a narrow range LED are a couple of the more common sources) So your apple will probably reflect a little green light. It is also probably a little shiny, and that has an effect.
There was a thread on this forum a while back that went into a lot more detail. The guy really pushed things to an extreme with very bright lights. It had pictures. But I can't find it right now.
The short version: Don't use 'pure' colors.
Add a little green and blue to your red. (does not take much - 0.01 or less might do it. Experiment.)
Make sure there is a little red in your 'greenish' light. (again, just a little.)
Also, might try bumping your specularity up a hair - Very few objects are perfectly Matte. You might have to increase surface roughness if you do this, so that you do not get reflections where you do not want them.
Of course, there are exceptions to these suggestions. If your green was supposed to be from a laser, you would want to keep it pure, but then black shadowed areas would be expected.
Hope this helps. I'd like to hear how it turns out.