No matter where, the elders of tribes are always idiots, aren't they? Getting paranoid over the slightest thing, and abusing their outdated rules to eliminate suspicions and not actual threats.
So you're convinced that the first group of unknown strangers you met, who your own shrine maidens (who can see the future) tell you are here to save you, are in fact evil.
Because a second group of equally unknown strangers told you so? What sort of logic is this?