This happened to me when moving to a new MacBook Pro. The only way to get TC/TM working again was to delete the OLD back-ups on the TC, i.e. erase them and then started completely fresh. Hence, suggest you try this, but ONLY AFTER you made another back up of your files.