I have just found some blog suggesting that compiling Flex application with Network Monitor on might cause Flex to try and call some local resources (even though application has been deployed on remote server). Sadly it was not a solution for my problem. It gave me an idea though, I should probably disable/remove settings of my debugger. Will attempt that later this evening (after work) and see how that will work.
Everytime that I had this error it was related with crossdomain...
Do you have any crossdomain.xml file at root folder of your Web Server?
Thanks for the tip. Yes I have crossdomain.xml file in root folder and my other projects are working fine. In that instance it probably has something to do with local configuration of debugger (or maybe some other feature). Note that system is trying to call my local gateway.php (this reference must have been compiled inside swf file during export of release build). Sandbox violation error is just a obvious consequence of that quirk.
Anyway, I have re-created my project in good old FB4.0 (if you will forgive its short-comings) and it works fine. I think I will wait with upgrading to FB4.5 for PHP. Its not that user friendly (it took me quite some time to setup PHP debugger in my WAMP environment) and its not that stable either (have had issues with refreshing of my PHP class).