Faits: A. C._ est inscrit au registre des avocats du canton de Genève. Le 9 novembre 2010, il a requis de la Commission du barreau du canton de Genève (ci-après la Commission) d'être délié du secret professionnel pour être entendu comme témoin dans une cause civile opposant D._ à B._ et A._. Le bureau de la Commission ainsi que la Commission plénière ont rejeté cette requête. Par arrêt du 11 octobre 2011, la Chambre administrative de la Cour de justice du canton de Genève (ci-après la Cour de justice) a annulé la décision de la Commission et renvoyé la cause à cette dernière pour qu'elle instruise la nature du mandat liant C._ à ses clients et détermine dans quelle mesure l'avocat était lié par un secret professionnel avant de statuer sur sa requête. Par courrier du 29 novembre 2011, B._ et A._ ont demandé à être appelés en cause dans la procédure engagée devant la Commission. Ils faisaient valoir que C._ avait été l'avocat des trois parties à la procédure civile dans laquelle il était appelé à témoigner et qu'en tant que bénéficiaires du secret professionnel de leur avocat, ils avaient le droit d'intervenir dans la procédure engagée devant la Commission pour s'opposer à toute levée dudit secret professionnel. Le 20 février 2012, la Commission a rejeté la requête d'appel en cause. B. B._ et A._ ont recouru auprès de la Cour de justice contre la décision de la Commission. Par arrêt du 8 mai 2012, la Cour de justice a rejeté le recours précité. Elle a retenu en substance que, dans une procédure en levée du secret professionnel, l'avocat sollicite d'être délié d'un secret dont il est le seul titulaire, de sorte que le client de l'avocat, même bénéficiaire du secret, n'a pas à être appelé en cause dans la procédure ouverte devant l'instance chargée de statuer. C. Par acte du 13 juin 2012, B._ et A._ déposent un recours en matière de droit public contre l'arrêt de la Cour de justice. Ils concluent à l'annulation de l'arrêt du 8 mai 2012, et à ce qu'il soit constaté qu'ils disposent de la qualité de parties dans la procédure portant sur la levée du secret professionnel de leur ancien avocat C._, le tout sous suite de frais et dépens. Subsidiairement, ils requièrent le renvoi de la cause à la Cour de justice pour nouvelle décision dans le sens des considérants. A titre préalable enfin, ils demandent que l'effet suspensif soit octroyé à leur recours. C._ s'en rapporte à justice sur le sort du recours. La Commission persiste dans sa décision du 20 février 2012. La Cour de justice renonce à formuler des observations.