Cannot change my email address

Tried changing my contact email address by adding the new address. Message states that it is already taken. So I then try a login with this new address, starting the lost password process and initiate a password reset to that new address. It is stated that an email is sent, but it never arrives, tried it several times. Tested the process with my current email address and the password rest email DOES arrive. There is clearly a problem, because I am changing email address on many of accounts and they do not have this failureā€¦ Please advise.