I recently purchased the game and tried to connect my sons account, and got the same 'opps! looks like that accounts is already linked'. Been bouncing around Mojang, MS and PSN support, and all have been blaming one another. His account was never linked to PSN, only switch and windows. My account is the only other PSN account we have, and I was able to connect that to my own MS account.
Hector - My sons account was created as part of a family account consisting of me as the organiser and him as a member. I was wondering if that was part of the problem. Do you have any additional information on this, or is that just an assumption you have made? I'm also not sure what you mean by creating a new email? Do you mean a new account or a new alias.
FYI - I have tried creating a new alias, and that did not work. I also quickly tried kicking him out of the family but it also had no effect (although I will try that again later as it may not have had a chance to propegate)
My update to this thread is that me and my kids have given up.
I have attempted to contact all involved parties involved and nobody seems to have any clues - I can't even get a straight answer about who actually controls / stores the info about what ms account is linked to which MS account. Mojang sends me to MS, who sends me to Sony, who sends me back to Mojang.
This issue, and the problems I had getting logins to work on the switch, makes me regret buying the game.