First of all, I'm extremely indebted to the following amazing blog posts and articles that helped hugely in rectifying the various ailments my UPS config was suffering from:
- Harbar.net: Rational Guide to implementing SharePoint Server 2010 User Profile Synchronization
- MSDN: Configure profile synchronization (SharePoint Server 2010)
- Clever Workarounds: More User Profile Sync issues in SP2010: Certificate Provisioning Fun
- When Technology Works: User Profile Sync provisioning remains in ‘Starting’ status (stops at ULS Eventid 9qh1 ILM Configuration: Configuring Certificate)
- Harbar.Net: “Stuck on Starting”: Common Issues with SharePoint Server 2010 User Profile Synchronization
- Delegate control for "Replicating Directory Changes" in Active Directory Users & Computers.
- Add the "Allow" right for "Replicating Directory Changes" to the Configuration container in ADSI Edit.
- Add the "Allow Logon Locally" right for the SharePoint farm service account in group policy.
- Ensure the SharePoint farm service account is a member of the local Administrators group while configuring the UPS.
One last thing I needed to do was to ensure that the FIM services (Forefront Identity Manager Service and Forefront Identity Manager Synchronisation Service) were set to "Delayed Start" in the Services applet.