I am not sure about the exact error that you mentioned. But, if i just look, i could see that timestamp has been missed in the security header. However i would copy the request message that i tried out...I use this message with SOAPUI to get the SAML Assertion from the STS service.. I guess this may help you.. If you are using this message, Please consider about timestamp value.. you can change it as it is not signed.
<soapenv:Envelope xmlns:soapenv="http://www.w3.org/2003/05/soap-envelope">
<soapenv:Header xmlns:wsa="http://schemas.xmlsoap.org/ws/2004/08/addressing">
<wsse:Security xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd" soapenv:mustUnderstand="true">
<wsu:Timestamp xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd" wsu:Id="Timestamp-1">
<wsu:Created>2014-03-04T17:53:57.033Z</wsu:Created>
<wsu:Expires>2014-03-04T17:58:57.033Z</wsu:Expires>
</wsu:Timestamp>
<wsse:UsernameToken xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd" wsu:Id="UsernameToken-2">
<wsse:Username>admin</wsse:Username>
<wsse:Password Type="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-username-token-profile-1.0#PasswordText">admin</wsse:Password>
</wsse:UsernameToken>
</wsse:Security>
<wsa:To>https://localhost:9443/services/wso2carbon-sts</wsa:To>
<wsa:ReplyTo>
<wsa:Address>http://schemas.xmlsoap.org/ws/2004/08/addressing/role/anonymous</wsa:Address>
</wsa:ReplyTo>
<wsa:MessageID>urn:uuid:258de3bc-c053-4b41-93d5-5d292a896b3a</wsa:MessageID>
<wsa:Action>http://schemas.xmlsoap.org/ws/2005/02/trust/RST/Issue</wsa:Action>
</soapenv:Header>
<soapenv:Body>
<wst:RequestSecurityToken xmlns:wst="http://schemas.xmlsoap.org/ws/2005/02/trust">
<wst:RequestType>http://schemas.xmlsoap.org/ws/2005/02/trust/Issue</wst:RequestType>
<wst:Lifetime>
<wsu:Created xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">2014-03-04T17:53:56.768Z</wsu:Created>
<wsu:Expires xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">2014-03-04T17:58:56.768Z</wsu:Expires>
</wst:Lifetime>
<wst:TokenType>http://docs.oasis-open.org/wss/oasis-wss-saml-token-profile-1.1#SAMLV2.0</wst:TokenType>
<wst:KeyType>http://schemas.xmlsoap.org/ws/2005/02/trust/Bearer</wst:KeyType>
<wst:Claims xmlns:wsp="http://schemas.xmlsoap.org/ws/2005/02/trust" wsp:Dialect="http://wso2.org/claims">
<wsid:ClaimType xmlns:wsid="http://schemas.xmlsoap.org/ws/2005/05/identity" Uri="http://wso2.org/claims/emailaddress"></wsid:ClaimType>
<wsid:ClaimType xmlns:wsid="http://schemas.xmlsoap.org/ws/2005/05/identity" Uri="http://wso2.org/claims/givenname"></wsid:ClaimType>
</wst:Claims>
</wst:RequestSecurityToken>
</soapenv:Body>
</soapenv:Envelope>