The exact same thing happened to me. I opened up my groups under contacts and saw that I had exchange contacts as well as icloud contacts. So, when I got my new phone, the only ones that transferred over where the icloud contacts. I took a recommendation and got an app that is called Contact Mover & Account Sync for Exchange, Outlook, iCloud, Gmail, Facebook, & Yahoo Email. It is free, but only moves 40 contacts. I paid the $3.99 to move all I had and it worked in just a few seconds. WELL WORTH IT and I have all my contacts back on my new phone instantly!!