1) I would make sure that you run the MS Update ( NOT windows update ! ) via the option in Windows update.
2) have you run DCDIAG and NETDIAG in verbose mode to see if this is a permissions issue ?
3) Run exchange Best practices analyzer ( BPA )
I hope this helps !