I encountered the same problem and I was able to resolve it with two solutions: First, I used the MMC snap-in "Certificates" for the "Computer account" and dragged the self-signed certificate into the "Trusted Root Certification Authorities" folder. This means the local computer (the one that generated the certificate) will now trust that certificate. Secondly I noticed that the certificate was generated for some internal computer name, but the web service was being accessed using another name. This caused a mismatch when validating the certificate. We generated the certificate for computer.operations.local, but accessed the web service using https://computer.internaldomain.companydomain.com. When we switched the URL to the one used to generate the certificate we got no more errors.
Maybe just switching URLs would have worked, but by making the certificate trusted you also avoid the red screen in Internet Explorer where it tells you it doesn't trust the certificate.