When accessing the web services in Flex you need a crossdomain.xml file in the root of the web server which hosts the web service. In the file you can mention whether to accept the connections from all the domains or the connections from the specific domains to be accepted.
Here the sample for a crossdomain.xml file which allows the access from all the domains.
1: <?xml version="1.0" ?>
3: <allow-access-from domain="*" secure="false" />
4: <site-control permitted-cross-domain-policies="all"/>
5: <allow-http-request-headers-from domain="*" headers="*"/>
For .NET guys, this is the exact similar version of the clientaccesspolicy.xml file we deploy in the root of the web server when working with Silverlight.