Email setup on iPhone 4S deleted contacts, reminders, and calendar dates
When you created the Exchange account, I think it ask you if you want to keep your contacts or replace them with the ones on the Exchange. And it surely works the same for calendar events and reminders.

It appears you asked your phone to replace your already existing contacts list with the empty one from Exchange.

Your best shot to get your contacts back is to restore a previous backup, and then, when re-setting your phone, be careful to what it's asking you.