I realize that this is an old-ish thread, but it's the one that popped up in search as I was sorting out this same issue, it's still relevant and I felt compelled to add.
My wife was happy to finally replace her iPhone with a Lumia yesterday; with this, we can remove all traces of itunes from our computers -- happy times. But before we could remove it, of course, we needed move all of her contacts over. For whatever reason, iTunes wasn't playing nice with her computer and wasn't syncing with the local Windows contacts so I took the easy route and added her contacts via syncing to her 'iCloud' account.
As I was sorting out her contacts, linking together various facebook/Outlook/iCloud/etc accounts, it dawned on me that this was a contact sync, NOT a contact import and that the 'iCloud' tag would always hang over the contacts from her old phone. This just didn't sit well with me -- the point of the move was to get out of the Apple ecosystem, not to have vestiges of it hanging around forever more. I don't want her contacts continually syncing with a completely cloud-based 3rd party service. 3 or 4 or 5 years down the line, I don't want her to have to try and remember what her iCloud login was... or to deal with a lapsed account... or deal with a compromised server...
In the end, I simply disconnected the iCloud account from her phone, which (or course) yanked out all of the contact info that had been added via iCloud, whether it was edited and linked to other contact entries or not (something that might have been concerning in a different situation). I then went with the other route suggested earlier and signed her in to icloud.com and exported/downloaded vcard info from her contacts. Her computer (Win8.1) was more than happy to add local contacts from that vcard file and, from there, sync to the new phone.
TL;DR: if you're not planning on maintaining an iCloud account, I would encourage you to not take the easy route by adding contacts via syncing to an iCloud account -- take a few more minutes to move contact info over properly by downloading the vcard info and importing it to your Contacts on your local machine.