On your phone go to Settings>iCloud and turn all data that you are syncing with iCloud (such as contacts, calendars, etc.) to Off. When prompted, be sure to choose to keep the data on the iPhone. After everything is turned off in Settings>iCloud, scroll to the bottom and tap Delete Account. Next, set up your new iCloud account using your new Apple ID and then turn iCloud data syncing for contacts, etc. back to On. When prompted, choose Merge. This will upload the data to this new account.