While this question was asked almost a year ago, it has received some up votes recently which may indicate that some other people are getting the same problem. Hopefully this answer can help :) Briefly speaking, the error doesn't happen in all machines but only in some of them. I guess it depends on what CSPs have been registered on a specific machine. Anyway, in my specific case, the certificate was generated with either "Microsoft RSA SChannel..." or "Microsoft strong cryptographic provider" as the CSP. I generated a new certificate but used "Microsoft Enhanced RSA and AES Cryptographic Provider" as the CSP and it SHA256 signing started working for me.
Some references:
https://social.msdn.microsoft.com/Forums/vstudio/en-US/e391ba75-ce6e-431c-bfc9-26a71ae1b033/sha256-signing-stops-working-in-net-45?forum=Geneva (as you can see, million thanks to Paul who helped me solve this issue)
http://hintdesk.com/c-how-to-fix-invalid-algorithm-specified-when-signing-with-sha256/