Can't change from gmail to icloud Apple ID
I am trying to change may Apple ID, which was created using a GMail email address, in to an iCloud email address.
However, when I enter my iCloud email to change, on my iPhone, it says "You can only add the @icloud.com address that is already on file in your account." But it already is on file.
and when I try it on a Windows PC (After signing out from iPhone), it says "Apple ID cannot be changed at this time, try again later."
What could be the reason for this?
However, the iCloud email I'm trying to change to, is a new one. So is that the problem?
iPhone 6s