Being a superbadge, particularly one that is now tied to an Salesforce University credential, I'm reluctant to give the full details of how to pass this challenge.
I can confirm that I got a very similar response from the web service when testing it from SOAP UI:
HTTP/1.1 500
Server: Cowboy
Connection: keep-alive
Content-Type: application/json;charset=UTF-8
Transfer-Encoding: chunked
Date: Thu, 20 Jul 2017 03:14:44 GMT
Via: 1.1 vegur
{"timestamp":1500520484619,"status":500,"error":"Internal Server Error",
"exception":"java.lang.OutOfMemoryError","message":"unable to create new native thread","path":"/ws"}
That JSON response seems to be particularly relevant. Is suspect there is something broken on their end. I've reached out to the Trailhead team about this. You could also use the feedback link provided directly in Trailhead.
I'd suggest focusing on the automated test cases and ensuring that they assert the correct outcomes.
Update
Just tried exactly the same request again today, it is looking much healthier.
HTTP/1.1 200
Server: Cowboy
Connection: keep-alive
Accept: text/xml, text/html, image/gif, image/jpeg, *; q=.2, */*; q=.2
Soapaction: ""
Content-Type: text/xml;charset=utf-8
Content-Length: 282
Date: Tue, 25 Jul 2017 21:59:38 GMT
Via: 1.1 vegur
<SOAP-ENV:Envelope xmlns:SOAP-ENV="http://schemas.xmlsoap.org/soap/envelope/"><SOAP-ENV:Header/>
<SOAP-ENV:Body>
<ns2:billProjectResponse xmlns:ns2="http://salesforce.com/th/invoice-web-service"><ns2:status>ok</ns2:status></ns2:billProjectResponse>
</SOAP-ENV:Body>
</SOAP-ENV:Envelope>