Just tried something that seems to have solved the problem. Things to note:
1. The synch process stops at the point where it encounters one contact with a problem. So you have to find that one contact. It seems to process the items in chronological order of the last modified date/time.
2. When synching, after it reads/processes the records on the handheld and Outlook, it gives you a dialog asking you to Accept/Cancel/Details of new additions. Click on details, then click on the first item...that is probably the one causing the problem.
3. In my case, the Outlook details looked fine, with first name, last name etc., but in fact in the translation from Outlook to Blackberry, the fields did not translate for some reason and to the Blackberry software, the contact "seemed" to be missing the required first and last names...
hope this helps.