Blackberry Sync Issues - Please help!

[infinitytech]

We have a client that has just put an SBS 2003 server with Exchange 2003 onto his network. He has a blackberry that needs to synchronize with a public exchange calendar and public contacts folder via the intellisync program while in the cradle. When the sync is set up, it starts to synchronize, and then you get the message "Unable to get an Outlook or Microsoft Exchange record." When you check the log, there is an error #4238 at the end of the log.

Here is what has been done to date to try to fix this problem....
1) Delete users mail profile and recreate a new profile
2) Close desktop manager, and delete Intellisync folder under "C:\Documents and Settings\(YOURUSERNAME)\Application Data\Research In Motion\BlackBerry\Intellisync" then restart desktop manager.
3) Completely uninstall the desktop manager software and reinstall
4) Tried to set up the synch with an off-line copy of the public folders (through the favorites)

Everything that I have found online says that one of the first two options should correct the problem, but alas, they have not. Here is some other information possibly of note for this problem:
1) Both folders are somewhat large (the contacts folder has almost 1800 contacts and the calendar has over 6800 items)
2) If a new calendar or contacts list is created in the public folders with only a few items in it, it seems to synchronize with no problems
3) Prior to the exchange implementation, the user had all of these contacts and calendar items in his personal .pst, and the synchronization seemed to work fine
4) He has full owner permissions to the public folders in question
5) He is able to synchronize with his own contacts and calendar within his Exchange account (even with the same amount of items in them)
6) His Exchange account is set up in cached mode

I am at a complete loss on this problem, and new to blackberrys! Any and ALL help will be GREATLY appreciated!