I have multiple (four actually) Apple ID's registered in Accounts. It turned out, that one of those accounts needed verification. I simply tried to log on with every account I have at appleid.apple.com until I got:
After verification, the problem was solved.