When you open your contacts tab, do you see something called GROUPS on top left? If yes follow below.
Check Settings>Mail, contacts, calendar> scroll down to contacts> ( There is Sort Order, Display order, short name, My info) do you see one more field called "default contact group" or "Save contact to"? This is the main culprit for your manually added contacts not saving to icloud but some other group.
If you do: open contacts again> Groups> uncheck icloud contacts. See how many contact are other than icloud. If list is small, write them on a piece of paper ( else export vcard 1 by 1 as email to icloud email) and delete them one by one.
Then go to settings>icloud>switch off contacts from icloud sync.
Go to contacts tab again and check if your contact list is clear.
Once clear, uncheck contacts sync from Facebook setting too. ( Settings> scroll down to facebook and turn off Contacts tab there).
After this, restart your phone and see if contact list is still clear.
Then turn on your contacts sync from icloud setting.