Да, у меня именно так с самого начало и было. Ввели в заблуждение некоторые ответы на stackoverflow

Код:
<?xml version="1.0"?>
<cross-domain-policy>
<allow-access-from domain="*" to-ports="*" />
</cross-domain-policy>
К сожалению не помогло. Загружал флешку, повторюсь, прямо на сам ВК и такая же проблема(
Добавлено через 35 минут
Выяснил, что для flash приложений oauth авторизация не требуется и запрос к API спокойно без ошибок начал работать. Только выдает json ответ

Код:
{"error":{"error_code":5,"error_msg":"User authorization failed: invalid access_token (4).","request_params":[{"key":"oauth","value":"1"},{"key":"method","value":"users.get"},{"key":"user_id","value":"4835..."},{"key":"v","value":"5.29"},{"key":"access_token","value":"e65811a40bd6d...............................805e0"}]}}
Передавал полученный sid

Код AS1/AS2:
var request:URLRequest = new URLRequest("https://api.vk.com/method/users.get?user_id=" + flashVars["api_id"] + "&v=5.29&access_token=" + flashVars["sid"]);