Under Settings > Mail, Contacts, Calendars on iPhone 4S, under each individual email account, do you also have Contacts toggled to on? That's in addition to having Contacts toggled to on under Settings > iCloud.
Then when I open the Contacts app on iPhone 4S, it shows all my email accounts under Groups. They can be sorted as All Contacts, All MobileMe, All iCloud, and each of my email accounts. My iPad 1 shows fewer ways to sort under the Contacts app, but all my contacts are visible on both devices, as well as my iPad 2.
I use Gmail and several legacy email accounts from other providers. Not sure how that mix might vary from yours, and how the effects might differ.