I managed to get this working finally. I couldn't manage to change it with any of the options I listed.
But what did work was using the FlexBuilder 3 interface and importing the WebService. Then using the code it called. Fairly significant work around, but it did work.