I just completed a project where SharePoint 2013 User Profile Service would show 'starting'. ULS logs reported "ERR_CONFIG_DB."
To solve the problem, I had to ensure the SharePoint 2013 SP1 was the "Refresh" version of SP1. Both SP1 versions have the same version number, but one is the correct one to install. I found a page via Google Search (keywords: josrod sharepoint patch reference) that is Joe Rodgers' SharePoint Patch Reference. The list has links to the necessary updates for fixing this problem.
Also, it was necessary to install a Cumulative Update more recent than April 2014. In my case I chose to install the June 2014 CU.
Note: The cumulative update install requires the .exe and two .cab files.
Note: The Microsoft Self-Extractor would not successfully extract these files unless I specified a top level folder in the root (C:\extractLocation).
Note: To download the CU, you will need to request a hotfix from Microsoft. This requires that you enter your email address. Soon after, Microsoft will email you links to the update. Be sure to check all three files of the CU/Hotfix.
After installing each of these I ran the SharePoint Configuration Wizard. Once it completed, I was able to install a User Profile Service Application and then start the User Profile Synchronization Service. The sync service started in less than 3 minutes.
I ended up using a PowerShell script I found online to automate the creation of the User Profile Service Application and Synchronization Service. There are several options for scripts.
I chose the one at this site:
The reason for the failure on the system I was working on was that I was using SQL Server 2014. SharePoint 2013 did not deploy the FIM database correctly with SQL 2014. The April 2014 CU is where the solution to this problem was first introduced (from what my research indicates).
To verify the configuration needed, I used the documentation on Spence Harbar's site: http://www.harbar.net/articles/sp2010ups.aspx
There is alot of information there. For me, it was key to setting up the necessary permissions. I was working with a test server, so I ignored the best practices that would keep me from directly logging into the server with the UPS account. The UPS account was a local administrator, farm administrator and had serverAdmin, sysAdmin and security admin server roles on the SQL server. If you are on a production server, I'd recommend using the script I referenced earlier from sharepointbjorn.com.
Also, in my case, the three user profile service databases were removed to ensure a clean slate for the starting point.