I first went to Settings > Mail,Contacts,Calendars > Exchange and turned Contacts on. I then went intoThis did the App called "Contacts" and selected Groups. I then selected "All Exchange", "Contacts" and "Suggested Contacts" (although I don't know what "Suggested Contacts" are)trick for me:
- Go to Settings > Mail, Contacts, Calendars > Exchange
- Turn Contacts on
- Go into the App called Contacts and select Groups
- Select All Exchange, Contacts and Suggested Contacts
After doing that, all the and the names of my contacts came back for recent calls and messages.