Make sure you are trying to hire your new retainers from the same city you started in at the beginning of the game. If you started as a Gladiator in Uldah I do not believe you can hire retainers at Limsa or Gridania.