Coldfusion: SOAP Security Header Problem

OVERVIEW
I need to make a secure SOAP request with Coldfusion , and I'm having trouble implementing the headers properly so the service can use it.

There are two structure examples I was given

Example 1:
This is a sample soap request:

POST /WebService/EmployerWebServiceV24.asmx HTTP/1.1
Host: stage.e-verify.uscis.gov
Content-Type: text/xml; charset=utf-8
Content-Length: length
SOAPAction: "https://www.vis-dhs.com/EmployerWebService/EmpCpsVerifyConnection"

<?xml version="1.0" encoding="utf-8"?>
<soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
  <soap:Body>
    <EmpCpsVerifyConnection xmlns="https://www.vis-dhs.com/EmployerWebService/" />
  </soap:Body>
</soap:Envelope>

Select allOpen in new window

Example 2:
An example SOAP authentication HEADER would look something like:

<soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xmlns:xsd="http://www.w3.org/2001/XMLSchema"
xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
    <soap:Header>
        <wsse:Security soap:mustUnderstand="1">
            <wsse:UsernameToken namespaces>
                <wsse:Username>username</wsse:Username>
                <wsse:Password Type="type info">password</wsse:Password>
                <wsse:Nonce>nonce</wsse:Nonce>
                <wsu:Created>date created</wsu:Created>
            </wsse:UsernameToken>
        <wsse:Security>
    </soap:Header>
    <soap:Body>
        <WebServiceMethodName xmlns="Web Service Namespace" />
    </soap:Body>
</soap:Envelope>

Select allOpen in new window

IMPORTANT
I was able to create a successful connection to this web service without including header information.
To use other functions I need a properly working header which works.
This is my code for the successful connection without the headers. (So you can reproduce it)

<cfsavecontent variable="request_xml">
<cfoutput>
<?xml version="1.0" encoding="utf-8"?>
<soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
  <soap:Body>
    <EmpCpsVerifyConnection xmlns="https://www.vis-dhs.com/EmployerWebService/" />
  </soap:Body>
</soap:Envelope>
</cfoutput>
</cfsavecontent>
<!--- Make Request --->
<cfhttp url="https://stage.e-verify.uscis.gov/WebService/EmployerWebServiceV24.asmx?wsdl" method="post" result="httpResponse">
  <cfhttpparam type="header" name="SOAPAction" value="https://www.vis-dhs.com/EmployerWebService/EmpCpsVerifyConnection" />
  <cfhttpparam type="header" name="accept-encoding" value="no-compression" />
  <cfhttpparam type="body" value="#trim(request_xml)#" />
</cfhttp>
<!--- Show Response --->
<cfdump var="#httpResponse#" label="httpResponse">
<cfdump var="#xmlParse( httpResponse.fileContent )#" label="soapResponse">

Select allOpen in new window

PROBLEM

When I insert my header into the request, then it throws me an error saying "code:InvalidSecurityToken"
(Replace cfsavecontent with this)

<!--- Define Nonce --->
<cfscript>
  strNonce = ToBase64(createUUID());
</cfscript>
<cfsavecontent variable="request_xml">
<cfoutput>
<?xml version="1.0" encoding="utf-8"?>
<soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
  <soap:Header>
	<wsse:Security soap:mustUnderstand="1" xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
		<wsse:UsernameToken wsu:Id="UsernameToken-1" xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
            <wsse:Username>ARIC1124</wsse:Username>
            <wsse:Password Type="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-username-token-profile-1.0##PasswordText">myPassword</wsse:Password>
            <wsse:Nonce>#strNonce#</wsse:Nonce> 
            <wsu:Created>#Dateformat(Now(),'yyyy-mm-ddThh:mm:ss')#Z</wsu:Created>
		</wsse:UsernameToken>
	</wsse:Security>
  </soap:Header>
  <soap:Body>
    <EmpCpsVerifyConnection xmlns="https://www.vis-dhs.com/EmployerWebService/" />
  </soap:Body>
</soap:Envelope>
</cfoutput>
</cfsavecontent>

Select allOpen in new window

OTHER SOLUTIONS I HAVE TRIED:
I have tried to use createObject + AddSOAPRequestHeader + cfinvoke but nothing seems to work for me

WHAT I AM LOOKING FOR FROM THE EXPERTS:
I want a complete cfm code file which would include my header that works.

*Email address removed by Netminder 15 Jan 2013*