To the eyes of everyone, FR's army went east to oust Sevastian (SA member) and help Bowie (SA enemy). The fact that the FR army refused to say its intent raised suspicion all the more. It doesn't matter that they turned around before getting there (because they got caught) -- the intent was there. It wasn't very surprising, then, that any realm with the FR army close by would be very apprehensive as to their goals -- especially when they keep quiet and refuse to say anything.