OK have you consiously made any updates to your Contacts in Lotus Notes or on your device?
In our environment with over 200 bberry users this happens all too frequently.
If you look at the dialog behind the error dialog, or open the sync log in Desktop Manager, which direction are the contacts going when it crashes, from Lotus Notes to the Device, or from the Device to Lotus Notes?
It's drastic but here's what we recommend to our users... Hopefully you know enough about your Lotus Notes environment to answer the client reconfiguration prompts
1) Make backups
Use Desktop Manager to backup your device (thus capturing the current contacts on the blackberry).
Shut down Lotus Notes and Blackberry Desktop Manager
Make an OS copy of your Notes.ini file
rename your names.nsf file to names.mmddyy
Edit your Notes.ini and remove everything below the $$HasLanPort=1 line, save the file.
Launch Lotus Notes, you will get prompted with the user configuration dialogs, enter your username, and home mail server and point to your user id file.
The client reconfiguration process should create a fresh new empty/clean names.nsf file for you.
Launch Desktop Manager and do a sync, you should get prompted with a "do you really wish to add xxx entries from the device to Lotus Notes".
And you should be all set until it wigs out again, which it will.
1) you can then shut down Lotus Notes and rename your notes.ini file back so you don't loose any needed configuration settings.
2) you can open the names.mmddyy file in lotus notes and do a Ctrl-A in the person view to get a doc count, do the same in your current names.nsf file and if there is a discrepancy, the missing doc is the corrupt entry in Lotus Notes that would not sync to the device.