Issue with Apple iCloud and iTunes account

Hello there,
I am using couple of Apple devices and created iTunes accounts. While creating the account I have used my work address (in USA) and with a private address in Australia. Now, my problem is that my work address is no more valid because I am moving out to another job. The work address is linked to iCloud account and it is keep asking my work email and password. Deleting the existing iCloud and creating a new one didn't work. I am not sure what are the alternatives here. Can somebody help me to resolve this confusion?
Thanks!
