Time Machine backup of renamed computer fails
Try to use tmutil inheritbackup:

sudo tmutil inheritbackup /Volumes/Data/OldHostname.sparsebundle


From man tmutil:

inheritbackup {machine_directory | sparsebundle}
        Claim a machine directory or sparsebundle for use by the current
        machine. Requires root privileges.

        Machine directories and sparsebundles are owned by one computer
        at a time, and are tracked by unique identifiers rather than com-
        puter name, host name, or ethernet address. The inheritbackup
        verb reassigns the identity of the specified item, reconfiguring
        it so the current host recognizes it during backups. When inher-
        iting a sparsebundle, the machine directory within will also be
        claimed.

        Inheriting is typically only one step in the process of configur-
        ing a backup for use by a machine. You may also need to use
        setdestination, associatedisk, or both, depending on the situa-
        tion.

        One machine can own multiple machine directories and sparsebun-
        dles, but it is ill-advised for them to reside in the same place.
        In such a situation, which will be chosen during a backup is
        undefined. As a result, inheritbackup will attempt to detect pos-
        sible identity collisions before making changes.


See also http://pondini.org/TM/B6.html.