Если вы обращаетесь к этому веб-сервису вручную с того же компьютера, он работает?
Есть ли способ, как вы могли бы использовать что-то вроде Fiddler для отслеживания сетевого трафика и выяснения того, что происходит?
Есть множество вещей, которые могут вызывать проблемы здесь, во Flex, в веб-сервисе и абсолютно везде между ними. Проверка журналов событий и журналов sharepoint также может быть информативной, но если они ничего не дадут, то, вероятно, будет полезен просмотр HTTP-трафика.