This seems to be a quite common problem. This is what I tried:
1.Central Admin - Services on server: Tried to start the user profile sync service (the user profile service was running). Result: Status changed to "Starting" for a few seconds, then back to stopped. I found no trace of errors in ULS or event log
2.I cleared the configuration cache (
link) - Still unable to start the service
3.Added the user running the service (in my case the sp_farm user) to local administrators.
Note: This sounds like a really bad idea for security reasons!!! - but I was facing this problem in a dev environment so I did not really care
4.I was still not able to start the service. Rebooted the server, and tried againg - now it came up