Became a paladin myself on Saturday.

Checklist:
1. Level 30 Gladiator
2. Level 15 Conjurer
3. Completed all gladiator class quests up to level 30
4. Talk to the person behind the counter at the Coliseum

That's it. Have fun.