Can you be more specific about where you mean "re-install" iCloud? Are you talking about on your PC? If so, what type of PC, and and Windows OS are you running on those?
You can have iCloud installed everywhere and signed in and turned on, but you do not have to have Contacts checked in the iCloud options dropdown list.
If all you were doing was changing your Apple ID email address, you should not have run into this trouble, so I suspect, that some additional steps must have been taken.
Before you changed your Apple ID, were you running iCloud? Were you syncing Contacts via iCloud? What, aside from your Apple ID has changed?
Which Apple ID is signed into the following places on your device:
Setings>iCloud
Settings>FaceTime
Settings>Messages>Send & Receive
Settings>iTunes & App Store
Do you have the iCloud Control panel downloaded to your PC? Was it there before?
When you were reporting that you got the "address had already been taken", what, exactly were you seeing on the screen, what screen were you on, and what were you attempting to do at that point?
I promise, changing an Apple ID, when done in the right order is an easy task to perform, so something went awry here unfortunately, which I'm sure now makes you guy shy. But, if we could just start from the beginning and go through step by step what you did, and then discuss step by step which would have been the easier way to do it, you may find that it is really much easier than it appears at this point.
It may take some time, but I would highly suggest that we really go step by step. One post, one step, unless we determine that two might be in order
Cheers,
GB