Faits: A. Considérant qu'il se trouvait dans l'impossibilité de respecter les prescriptions relatives au travail du dimanche pour certains de ses services, l'Aéroport International de Genève (ci-après l'Aéroport) a déposé, le 28 octobre 2010, une demande auprès du Secrétariat d'État à l'économie (ci-après Seco) tendant à déroger à la législation sur le travail et visant à faire passer de 26 à 20 le nombre minimal de dimanches de congé pour une partie du personnel au sol du secteur de la navigation aérienne, avec effet au 1er janvier 2011. B. Par décision du 25 février 2011 (FF 2011 2166), le Seco a accordé à l'Aéroport une dérogation valable du 1er janvier 2011 au 31 décembre 2013. Selon celle-ci, le personnel au sol du secteur de la navigation aérienne travaillant auprès des services "sûreté passagers, AAU (plans de vols et informations aux pilotes), AMS (guidage au sol des aéronefs), APS (positionnement des aéronefs au sol), Piste (transport des passagers et conduites des véhicules destinés à guider des aéronefs sur la piste) et SSA (section feu, surveillance, transmissions)" bénéficiait d'au moins 20 dimanches de congé par année civile pouvant être répartis à intervalles irréguliers sur l'année. En contrepartie, une compensation de 25 % de la durée du travail effectué pendant la période du dimanche dès le 23ème dimanche travaillé dans l'année était prévue. A l'encontre de cette décision, le Syndicat suisse des services publics (ci-après le SSP) et A._ ont recouru conjointement auprès du Tribunal administratif fédéral. Après avoir retiré l'effet suspensif, cette instance a, par arrêt du 22 décembre 2011, admis le recours et annulé la décision attaquée. C. Contre l'arrêt du Tribunal administratif fédéral du 22 décembre 2011, l'Aéroport forme un recours en matière de droit public au Tribunal fédéral. Il conclut, sous suite de frais et dépens, à l'admission du recours, à l'annulation de l'arrêt attaqué et à la confirmation de la décision du Seco du 25 février 2011 accordant la dérogation requise. A._ et le SSP proposent le rejet du recours, sous suite de frais et dépens. Le Tribunal administratif fédéral a renoncé à prendre position, renvoyant aux considérants de l'arrêt attaqué. Le Seco n'a pas déposé d'observations. Par ordonnance du 8 mars 2012, le Président de la IIe Cour de droit public a accordé l'effet suspensif au recours. Le 26 octobre 2012, la Cour de céans a délibéré sur le présent recours en séance publique.