I would suggest connecting the drive directly to you Mac, then use Disk Utility to verify/repair the disk and backups. You need to do two things - verify the partition and verify the sparsebundle containing the Time Machine backup for your machine.
First off, use Disk Utility to verify and/or repair any partitions on the drive.
Next, Disk Utility can perform its First Aid repair on a mounted sparsebundle. Either double-click on the sparsebundle in the Finder, or drag it to the device list in Disk Utility, select it, then mount. Then you can select the mounted drive containing your backup, and run First Aid verify or repair.
The reason I suggest connecting the drive directly to the Mac is to both greatly speed up the process of checking the sparsebundle, and to allow testing the partition itself.
Hope this helps - I've never seen that paticual Time Machine message before. It might be some error related to network backups (and their use of sparsebundles). Most of the time, my backups are to a hardwired drive, which doesn't use sparsebundles.
