Nasty error message that Apple deals with here:

http://support.apple.com/kb/TS1998

Except that it seems to assume that there are 2 computers being synced and one of them is the more up-to-date. The problem I met with a client was that he had 2000+ contacts that showed up nicely on his iPhone, but none at all on his only Mac.