Hi Alex,

Not sure if this is the answer, but it helped me in a similar situation.
Taken from:
"HOL202 Exploring WSE 3.0 Security " Hands-On Lab

8.    Ensure that the web service will have access to its private key in the
certificate store. This is an important step – if you forget to do this,
clients will likely see faults including rather cryptic error messages such
as “Bad Key”.
a.    Run the WseCertificate3.exe tool which can be found in the \Program
Files\Microsoft WSE\v3.0\Tools directory.
b.    For Certificate Location, choose Local Computer.
c.    For Store Name choose Personal.
d.    Click Open Certificate and you should see the WSE2QuickStartServer
certificate that you installed a few steps ago. Select it and press OK.
e.    Press View Private Key File Properties to bring up the properties for the
private key for the certificate. Select the Security tab.
f.    If you’re running on Windows XP, your web service will run under the
ASPNET local account by default, so grant read access to that account by
pressing Add, typing ASPNET, and then pressing OK.
g.    If you’re running on Windows Server 2003, follow the same steps, except
specify “Network Service” instead of ASPNET. On the server OS, web services
run as Network Service by default.
h.    Press OK to commit your change, and close the tool.