I have already Re-Created the Key.
I then removed the old one from the job, Saved the job, re-opened the job and attempted to add the new key.
I also added the renamed account explicitly as a Logon Account in BE, then set it as the Default Logon Account, then shutdown BE, logged off the server. Logged back on, opened BE and attempted the process of Creating and Assigning the key. No success.
Is there somewhere else that needs to be updated?