It's possible that one or the other thinks the system is on GMT. Is the time change the difference between your time zone and GMT time? I seem to remember that by default, Fedora will choose the system being on GMT and if you don't catch it during installation, your time might always be off that.
Is it Fedora that is off, or Windows?
If that is the case (that is, with one of them giving GMT time) then there's nothing wrong with your CMOS. Otherwise, if the time difference varies randomly, there is a good chance that replacing the battery will fix it.