If it has actually changed, and you didn't change it, how do you log in to iCloud? And how did you find out it had been changed? You mentioned an email, who is it from (you can right click on the "FROM" address in Mail to get the full sender information)?
WARNING: If you abandon the AppleID you have and create a new one, all of the software purchases with that original AppleID will be lost and you will have to purchase new licenses/copies with the new AppleID, in addition to changing it on all of your Apple devices (Mac, iPhone, iPad, etc.).
What may be happening is that you are being spammed by someone hoping to get you to respond to the email so that they can actually get your password, or get you to divulge personal information so they can do further damage. The don't actually have access, and cannot actually change your password, but if you click on any link, or follow their information you would fall into their trap.