what i think that you had contacts in Outlook and in the device and when you activated iCloud
you did merge and not replace, as resolution you need to desable contacts in the settings of iCloud on the iPhone
and then sync contacts via iTunes.
after that activate contact but you need to do replace (before all this check in www.icloud.con if the contacts are not in double also because if they are you need to remove manually )
i hope this help.