Python and computing checksums
Probably there is no need to refactor the method as it represents quite clear decision tree. Breaking it down into smaller methods will cause readability problems.

Just make sure you have unit tests covering each outcome and that there are no cases, which the code doesn't handle.

If you definitely want to refactor, I propose to add a method like this:

def _check_log_writesums(cond, logmessage, rewrite=True):
    if cond:
        if logmessage:
            self.logger.debug(logmessage)
        if rewrite:
            self.write_checksums()
        return True
    return False


Then you can call it like this:

    if filename in stored_checks:
        return self._check_log_writesums(stored_checks[filename] != checksum,
                                         "",
                                         rewrite=True)


Maybe the name can be better (_update_checksums or _do_write_checksums).