GMail never recycles old usernames, whether they have been deleted or not, so your test above proves nothing, I'm afraid. 

afox8888888 -

If you have deleted the account that you used to set up your Android, then the only way to replace that old account is to factory-reset your phone. As you say yourself, andrea.fox415 is indeed set in stone for your phone. 

When you try to sign in to your new account, what exact error message do you receive? How are you being asked for this old password?