Two common thing that you can check to try and troubleshoot will be to confirm that the device has the available memory. BB does begin to delete old emails, calendar entries, etc..., to make room for 'newer' items. Next, you will need to check the contacts themselves. A contact cannot sync unless it has at least one of the three fields filled, first, last, or company name. If not, the sync will stop. So the information you found with the service books is a good start, though it will not help without confirming the actual contact list.
I'm actually lost...