Hi Djordje,
I never met such a problem, but personally I would have try to double-check that web service under development reports correct problem and capture the request sent by TestComplete using Fiddler, WireShark or any other http-capturing tool.
Wouldn't you mind to try to capture the problematic request (and the good one, to have something to compare with) and either post it here (along with the WSDL file of the tested web service) or open support ticket (http://support.smartbear.com/message/?prod=TestComplete) and provide Support with the same details?
