I seem to recall that the two soldered-on PRAM batteries on the 6-slot II-series Macs will cause this behavior when they're flat.

Am I right that they are what you replaced patatas?