連絡先がiCloudに反映されない

それらの連絡先は、iphoneのicloudのところに登録してますか？連絡先はアカウントの設定によっては、icloudだけでなくgmailなど他のメールサービスと関連づけられてる場合もありますので、登録する際には、間違いなくicloudに登録するようにします。

icloudで連絡先オンというのは、icloudの連絡先と同期するという意味です。これはバックアップ（icloudでバックアップをオン）とは別の話です。連絡先でicloudと同期をオンにしてる場合には、連絡先はicloudにはバックアップされません。ただ、同期は、iphoneをwifiに繋いでる時のみに行なわれますし、条件が揃ったらすぐ優先的に始まるというわけでもありませんので、icloudの連絡先で新しく登録したものが確認できるようになるには時間がかかる場合があります。少なくとも一晩くらいは置いてみてはどうでしょうか？

そうですね。

gmailの方に入ってるなら、gmailの連絡先と同期してます。iphoneでそれらの連絡先をicloudの方に移動してやれば、icloudと同期するようになります。なお、icloudの方に移動すると、それらの連絡先は、iphoneでは同じ連絡先がダブって表示されますが、それは正しい挙動です。２重に表示されてるときにgmailの連絡先のみを表示させて、それらを消去すれば、icloudとの同期のみになり、ダブって表示されることは無くなります。

まずはその外部サービスを教えていただけますか?

>今回移行したものはgmailのすべて

追加した連絡先は、gmailにある。

つまり、iCloudとは無関係な場所にあるということです。