Hey Caele, I've exactly the same problem. WebServices are working like charms in debug mode, but if I try to export a release version, it won't work anymore...
Understand the SandboxType of flash player before getinto this issue.
While inside the bin-debug, your sandbox type is LocalTrusted. This will allow access to external system,
When go go for the deployment it wont works, cos you sandbox type will be different (say Network with Local)
The above URL will expain the security concept