Are you sure that you get a first mission for Caralis or Patavium? I've been playing on VH/VH for a while and got the same missions as the Roman factions all the time.