If you have more than one email account configured on your device, make sure to correctly set the "primary" account by going to Settings->Mail, Contacts, Calendars and them scrolling down to "Default Account". Now, when you login to the iCloud website via a computer, are you viewing all contacts or just a certain group? Finally, make sure contacts is enabled in the iCloud settings on your device.