Bob Blumenkranz replies that it is possible that there is a difference in the startup sequence in the newer OS versions such that more battery power is required to successfully startup. He adds: "In general the voltage of the clock battery was not a problem in the past because it drew micro-amps and would last for several years. The 6400 may have a different clock backup circuit that requires much larger battery capacity. This is apparent from the overall size of the battery now being used. The change in the operating system may have a direct affect on the battery life if that is the case."
My reaction is that the jury is still out on this one. Apple says it knows what the cause is, although they declined to reveal it. In any case, while I suppose there are worse problems you could have than having to wait an extra 30 seconds for your Mac to startup, let's hope Mac OS 8.1 fixes it.