Am I understanding correctly that you are not using a needle valve? Magnetic valve = solenoid?
Dont have a needle valve on my system.. now found the problem =)What needle valve are you use? That solenoid is fine, it's just turn on or off the Co2, it doesn't actually control how much Co2 is let out.
Include the picture of the needle valve or the entire set up, I'm thinking you're using an inline needle valve too?
Thanks will doI'd like to recommend having a read here: http://www.plantedtank.net/forums/showthread.php?t=107312
Particularly see #3 about needle valves. That is what you need to make fine adjustments and will let you raise your working pressure to whatever is needed to make it stable.
Edit: Or maybe flyinghellfish is correct about an inline nv.