Just reproducing Arphahat's and Camp Freddie 1969 protectorate posts from the .com forum, just in case it disappears. I know that Sim already linked to the screenies, but some of this text might be useful.

Please note that I have not personally confirmed any of Arphahat's work, although beezer says that he has.

Arphahat.
There is a simple technique for winning the game. Simply siege a city of a rival faction, immediately lift the siege, save the game, reload the game and then have a diplomat ask the rival to become a protectorate. This works every time, without exception! Look at my glorious conquest in picture form below.
www.stampor.com/Rome/exploit.html
EDIT: here is a link to a list of the images, instead of loading all at once, if it helps www.stampor.com/Rome/exploit_links.html

Question.
One question I have is what happens when 2 of your protectorates go to war with each other. Are you forced to choose 1 and thus you loose the other???
You lose one of the protectorates. But, no problem; just make sure you keep a diplomat next to each of the factions. If you ever lose a protectorate, simply save, reload and ask again.

Camp Freddie 1969.
I found that if I declared war then immediately asked for a protectorate (before hitting end turn), I would always get one due to the much lauded re-evaluation feature.
However, I also tried it on the Thracians, with whom I've been fighting a long war. I outnumber them by a huge margin and regularly spank the armies they send my way with losses that are >10:1 in my favour. I've always been suprised that they don't accept being a protectorate in normal gameplay.
So I asked them after a reload - and they refused! Could it be that the auto-protectorate 'feature' is broken?! Then I looked at the refusal message:
"We cannot accept such generosity, since we have nothing to offer in return".
That's right folks. They refused because the AI re-evaluation decided that my demand of making them a slave nation was 'too generous'. They found themselves not worthy of my benevolent (er, yes, benevolent) rule!
After moving on a turn, I asked again and got the normal response of, "We are proud of our freedom and do not give it up lightly...."
So the re-evaluation feature seems to be totally underestimating the strength of the AI nations.