Have you turned the difficulty way up? Maybe that's it. I do agree with the spy thing, though--they're useless because they almost never successfully infiltrate cities. Even worse are assassins--you'd think Lysimachos the Killer, the best assassin alive, would have more than a 1% chance to kill some Roman nOOb camping in hostile territory with only a handful of bodyguards :(