Adding two more months (Januarius and Februarius) wasn't the problem and they probably always have existed, but starting the year with January instead of March was. This decision was made in 601 AUC (153 BCE) much later than the legendary king.