Just wanted to make an update to this thread. I recently switched to an 8310 and upgraded the stock AT&T OS to the new Rogers 22.214.171.124 OS.
Since I was running DM 4.2.2 sp2, I figured that it was time for an upgrade to DM v4.6. As soon as I attempted to set up the Sync, I got the same exact error message as before.
Following gqstatus's advice resolved the issue. A simple search at RIM's support website brought up the appropriate fix as well. Thanks again, I appreciate your help!
Here is the link to the RIM support site's fix, as also posted above; Microsoft Outlook sync issue fix