Have you tried resetting the power manager? Instructions are here:
http://support.apple.com/kb/HT1431?viewlocale=en_US
I would also zap the PRAM (though changing the PRAM battery would have effectively accomplished that) and reset the NVRAM, just for good measure.
Zap PRAM: reboot while holding down command, option, P, R. Keep holding them down through 3 chimes.
Reset NVRAM: reboot while holding down command, option, the letter O, and F (this boots you into Open Firmware, which only works on PPC Macs.) You'll get a white screen with black text. When the text stops spewing, type "reset-nvram" and Return. Then type "reset-all" and Return, whereupon the computer will reboot itself.
If that doesn't help, you may have a hardware problem of some kind.