Ok this is what needs to be done.

Conjurer at LV15
Gladiator at LV30
All Gladiator's guild quests must have been completed.
Once these conditions are met you should be able to talk to receptionist for Paladin Quests.

In fact you can just do all the GLA quests and still talk to receptionist but it would still require you to have Conjurer at LV15 and you being a LV30 GLA to talk to her.