Modification du bail par l'agence, un an après sa signature

Bonjour, nous avons signé il y a un an un bail pour la location d'un appartement (T3). Celui-ci est accompagné d'une place de parking. Lors de la visite l'an dernier, nous avons demandé au commercial s'il était possible d'avoir 2 places de parking couvertes plutôt que celle qui nous était proposée. Il nous assure qu'il n'y a aucun problème, la résidence n'avait que six mois ("premiers arrivés, premiers servis" nous a-t-il dit). Nous signons alors le bail en notant dessus les deux places de parking couvertes.
Un an après, l'appartement auquel était normalement attribuées les deux places vient d'être loué : le locataire nous demande de les libérer. Après discussion, il nous montre son bail sur lequel lui aussi a les deux places inscrites. Nous contactons l'agence (Akerys) qui nous annonce que le commercial ne travaille plus pour eux et que nous devons libérer les places immédiatement. Pouvons-nous faire quelque chose, sont-ils dans leurs droits ?
Merci.