Strange. I re-ran the job a 2nd time, and the restore of Database A completed normally this time (using a new DIFF backup), but the restore of Database C failed with that message.

Maybe the backups are getting corrupted somehow during ftp to the target servers.