Double check the docs first just in case you did miss a step and have a search coz i know I have seen this posted before. We are Exch2K3 but I know there is a bit of shell messing for Exch2K7 perms.
It actually sounds like mismatched CDO.dll files to me as that is usually the cause of the one-way sync issue but do check your work first. When you check the CDO.dll, check all BESs and Exchange boxes, they should all be the same and the latest.
I was a BES and Exchange admin once.
Then my world turned Blue.