The problem was solved by adding a parameter

Parameter WSADDRESSING = "TRUE"

Once we did that the web service call contained the proper soap action information and the call worked.