OK, I'm starting to get a complex! I've posted to the Adobe Flex forums 3 or 4 times now and have only had a reply once! I know these forums are monitored by Adobe folks. I can't believe nobody has a suggestion or some kind of pointer.
As far as I know flex has issues working with xFire or Axis (I can't remember which one is actually) maybe this is the reason why the other team has no problems... either way, this might also help
From the Flex Docs (Using WebService component)
The Flex web service API generally supports Simple Object Access Protocol (SOAP) 1.1, XML Schema 1.0 (versions 1999, 2000, and 2001), and WSDL 1.1 RPC-encoded, RPC-literal, and document-literal (bare and wrapped style parameters). The two most common types of web services use remote procedure call (RPC) encoded or document-literal SOAP bindings; the terms encoded and literal indicate the type of WSDL-to-SOAP mapping that a service uses.
try playing with those properties to see if you've got any luck