I actually had that issue initially, along with my contacts not sync'ing w/ Facebook contacts, etc.
I think its just a timing problem, as within a day or so - - I think two days - - it was all there. Not sure about you, but my exchange contacts had upwards of 5000+ entries, so it might have been the culprit was the size? But it did sort of, work itself out.