Great! Thanks for all the responces.
I'm sure the namespaces are part of the problem and Soapui looks soooooo helpful.
It turns out, with some comparison testing between my output and the PHP example, I also found my header Request Signature wasn't being generated correctly. It wasn't putting it through the Hmac SHA1 algorhythm at all! Now that I've fixed that, I can get to the bottom of the XML problems.