This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
Have you tried adding a handler on the server side of service B that logs all the requests?
I would log them to a file and then try to find request(s) for which error(s) occur, so see if there is a problem with the data reaching the web service or if the problem is in the service itself.
If there is no problem with the web service (which means that there are requests that are bad that reaches the web service) then I would continue trace backwards to see where the request(s) become corrupted.