OK, firstly your prob is almost certainly NOT your psu, I'll explain. I've got EXACTLY the same prob as you in as much as, when I overclock the memory, even by 1 mhz, I get a "green" screen and I have to restart. The core clocks fine up to 575mhz and the card runs fine at these settings (memory at stock). When I first got this card, HIS X1800XL, the memory would go to 550mhz no probs. It was when I started messing with the atitool beta overclocking software that I got the same prob as you, unable to overclock the memory, even by 1mhz.
My psu is enermax noisetaker 485w, and I've been running fine with the above settings for weeks now. I personally think the memory problem is bios related as I've tried so many things in an attempt to find the cause, that the bios is the only thing left. I'm looking into getting the correct flashrom (I already got the bios, same as the sapphire versh) and as soon I get the info I need, I'll give it a go.