Software Update keeps on failing after upgrading to Mountain Lion

I have updated my macbook pro to Mountain Lion and since then software Update keeps on failing. It comes up with "No new software available." I have tried upgrading iPhoto, iTunes and OS X itself and all of them are failing with new software available error message. What might be the issue?? Has anyone faced the same or has any idea about it???

I am having same issue in my case, I have checked out my install log and I see below things:

Oct 18 09:51:17 ... Software Update [1871]: Failed Software Update - trust evaluation failed in SecTrustEvaluate with result: 3
Oct 18 09:51:17 ...Software Update [1871]: Can't load distribution from https://swdist.apple.com/content/dow...SKkrfTC8hC83GZ zR3YCpDs57Bq/041-5409.English.dist.gz: Host cert invalid or otherwise insecure download

It seems as if there is some issue with my certificates but I don’t know how to deal with it.

I have just checked out my log and have found same errors there. It seems as if Software Update is coming up with app store but is accessing some other site for update giving "No new software available" error message. I have been looking after a fix for this issue since yesterday and haven’t got any luck. Let me know if you get any update on this.

I want to know if you had made clean installation of Mountain Lion?? In case you had not, then I will suggest you to reinstall Mountain Lion first.

Try this and check out if it makes any difference:
In Finder menu > Go to /var/folders/
Now check out for com.apple.AppStore, once you get it delete that folder and relaunch Software Update and see if it works fine.
Some people have mentioned this trick to be working out for you, so even you both can try it out, best of luck.

Reinstalling Mountain Lion won’t make any difference. I have already tried that out.
I have tried deleting com.apple.AppStore and relaunching AppStore but I get same error message again. Other than these things I have tried deleting .plist file for Software Updates and have tried resetting PRAM and system clock as suggested by others but no avail. I just can’t get Software Update working.

Since you have mentioned that the issue appears to be related to certificate, why don’t you try reinstalling certificates for Software Update along with the root certificates. I am not sure if it might help or not but it will be worth a try. Just try it out and post back the result you get, best of luck.

I have tried reinstalling certificates for Software Update along with the root certificates without any luck. Is there anything that I can try out further?? Is this a bug in Mountain Lion? I can’t think of anything else that might be causing this issue as I have made clean installation of Mountain Lion.

I have checked out for this issue and have found it to be because of keychain, in order to fix it try out below steps:
Open Keychain Access > Preferences > Click on “Certificates tab” and make below changes.
Set "Online Certificate Status Protocol" to "Best Attempt".
Set "Certificate Revocation List" to "Best Attempt".
Set "Priority" to OCSP.
Once you are done with above changes, close Preferences window, go to System keychain and check out if there are any certification authorities with non-standard settings. If you see any then reset each of them to default. You have to Right-click on each entry, select "Get Info", Expand "Trust" list and select "Use System Defaults" for "When using this certificate".
Now restart your system and try Software Update again.

You have done clean installation of Mountain Lion then you should reinstall certificates for Software Update by following above described steps by Evoldo.