Sounds like someone stole your password, logged himself in the service using your password and then changed the old password to a new one.
Did you get an Email, which reads that your password has been changed? If you got one, there should be the option to reset the password and/or call support. Do both.
If you haven't got an Email, get in touch with Apple Support and explain them your problem, they will know what to do.
Here you can contact Apple Support: https://getsupport.apple.com/ServiceOptionAction.action
I don't suppose to reset the password yourself, since you probably got hacked, which is an official crime, so you should tell Apple about it.
To prevent such an event in the future, use strong passwords containing letters AND numbers. Never use the same password for two different websites or services.
You can find a list with the most popular passwords here(Don't use them!!): http://gizmodo.com/the-25-most-popular-passwords-of-2014-were-all-doomed-1680596951