You don't have to create new app id simply what you have to do is add new features to existed app id.
If you go to apple development portal--> login to your account there you will see.
Click on Certificates,identifiers & profiles--> Click on Identifiers--> Then Click on identifier to whom you want to add new feature say "iCloud"
At the bottom you will see Edit button
Click on edit you would be taken to a new screen where you can add new feature iCloud to it.
Now here are few points that you have to remember.
You would have to alter you all certificates for this identifier and then regenerate new ones. Remember all provisioning profiles,certificates need to be regenerated for this App Id.
I have done so many times further you can ask i will help you.