My idea was to give them +10% attack and defense in cities, and drop the strength to 7. They are still ungodly strong against cities and for holding them, but in the field they can be beaten by axemen, and thus have a counter.
I don't think giving them a melee bonus is fair unless you consider something like 6 Strength with +25% vs. melee...but even that's pretty strong. I would go with the increased strength idea that Firaxis has used, but just tone it down a little bit.
@Those who say the Praetorian isn't overpowered: I think its strong, definitely, but overpowered...maybe. I've come out against the praetorian before, but recently I haven't bordered Rome early on, so I can't say from 2.08 experience about the balance. Even still, the fact that nothing can counter it in the ancient or classical era is somewhat perturbing.
Also, at Armorydave: it's convenient you ignored the fact that a praetorian will likely win that match. It would probably take two axes to destroy a praetorian, which means you have to double the investment cost there. Typically, with a counter, you are favored to win in a one-on-one match. That isn't true of the axe-praetorian fight.