"Verify Valid Certificate to Authenticate Microsoft Dynamics Lifecycle Service"
After spending hours and days to resolve this issue, it turned out really a Clock Setting Issue. I have done everything thinking that It can't be just clock that's throwing this Cert validation off. But believe me it was.
Step 1 - Check your clock to make sure it is reflecting the correct time.
Step 2 - Check your time Zone if it is a correct time zone
Step 3 - If Above both aren't correct, make sure you restart your server and correct time in computer BOIS setting (Atleast correct the date and time there) -- This is mandatory step as if computer gets restarted, it will throw off your clock settings again.
Step 4 - Now you can adjust the time and time zone of your computer and it will stay correct even after your computer restarted.
Step 5 - Now create a new certificate and run the setup
It worked for me and I am hoping it will help other folks as well. There is another resolution to this problem posted on our blog, if this solution didn't work for you, please try the other solution " Uninstalling a security update"