It should normally work after going through the steps that you followed. If it is not working however pleasem get through these ones:
Go to Tools -> App. Manager, choose Options -> Settings and set Software installation to All and Online certif, check to Off.
By the way, is it a certificate expired error please?
If doing this doesn't solve the problem, I will advise to make a back up and reset the phone through the below:
If this also doesn't work then try re-updating ur software.
Hope this solves the issue.