In a SharePoint 2010 installation that I recently worked we got Failures in the log when trying to perform a User Profile Syncronication. The account, domain, etc where all correct. Having Googled a bit we thought that it might be a FIM related issue.
Opening the Syncroniztion Service Manager (C:\Program Files\Microsoft Office Servers\14.0\Synchronization Service\UIShell\miisclient.exe) we found the error: "The management agent failed on run profile "DS_FULLIMPORT" because of connectivity issues." Why??
We went through the checklists, guidelines and what we had done, and everyhing looked correct; correct user account, we've set the Grant Replicate Directory Changes permission on the cn=configuration manager, the FIM services where running correctly, etc.
But of course I had missed one step (there is always something :-( ): Granting Replicate Directory Changes permission on the domain.
So you must add Replicate Directory Changes permissions both on the domain AND the confiugration container!
It's all documentet on TechNet: Configure profile syncronization.