The issue was not with my WSDL, but rather with the PHP framework we were using and how it was setting up the rest of the web service message. In the Input and Output section of the WSDL, it was assigning an encoding to the soap element. I created a sample Web Service project with VS, looked at how it does it, and changed this PHP framework to do the same thing. My soap element now looks like this:
<soap:body use="literal" />
After changing this, Attributes worked perfectly it seems.