I'm sticking with my "cheap power supply" and "firmware update" higher voltage threshold theory at this point.
Sounds like a pretty good theory to me. We would need an oscilloscope on the output of the PSU to be certain, but I have seen some pretty strange behaviour from electronic gizmos when using particularly noisy power supplies. SD card lock-ups would not surprise me in the slightest.
The fact that it works perfectly on the battery suggests you are most probably correct.
My guess is that there is some sort of high frequency noise getting through to the camara from the PSU, so perhaps a few filter caps across the output might fix it.
Alternatively, try a different brand of cheap PSU. The quality varies enormously across the range of available PSU. Some actually work surprisingly well (where the design has been pinched from a higher cost product perhaps), others are dreadful. One or two are down right dangerous.
