Faits: A. F._ a été engagé le 4 janvier 2002 en qualité d'auxiliaire par les X._ pour une durée déterminée, jusqu'au 3 juillet 2002. Selon le contrat signé par l'intéressé, cet engagement était soumis aux dispositions légales et statutaires relatives aux conditions de travail du personnel des X._. La fonction de F._ était définie ainsi: "coordinateur/formateur support applicatif/9 à la direction informatique de gestion". Par courrier du 12 juin 2002, les X._ ont prolongé le contrat jusqu'au 31 décembre 2002. Le 7 juin 2003, ils l'ont reconduit jusqu'au 31 janvier 2003. Le 16 janvier 2003, F._ a participé à un entretien d'évaluation et de développement des compétences en présence de ses supérieurs hiérarchiques. Ses prestations ont été jugées excellentes. Son responsable hiérarchique s'est prononcé en faveur de la poursuite de la collaboration, avec une évolution vers la fonction d'analyste-programmeur. Sans interruption, le contrat de F._ a encore été plusieurs fois prolongé. Par courrier du 11 novembre 2003, les X._ ont reporté pour une dernière fois son échéance au 30 juin 2004, précisant qu'il s'agissait de la dernière prolongation possible. En février et en juin 2004, F._ a sans succès postulé pour deux emplois au sein des X._. L'engagement de F._ a comme prévu définitivement pris fin le 30 juin 2004. Le poste a cependant été peu après remis au concours et F._ a ainsi été réengagé le 17 août 2004 en qualité d'auxiliaire. Selon le contrat signé à cette occasion, l'engagement devait débuter le 1er septembre 2004 pour s'achever le 31 août 2005. La fonction était identique à celle précédemment exercée. En novembre 2004 et janvier 2005, F._ a en vain déposé sa candidature pour trois postes différents, toujours aux X._. Le 28 juin 2005, les X._ ont prolongé le contrat de F._ jusqu'au 31 août 2006. Le lendemain, un nouvel entretien d'évaluation a eu lieu. Les prestations de F._ ont derechef été qualifiées d'excellentes, de sorte qu'il a été proposé de lui octroyer la fonction d'analyste-programmeur, ce qui fut fait le 12 juillet suivant. En juillet 2005 et en février 2006, F._ a répondu à des offres pour des postes ouverts au sein des X._. Par courrier du 20 janvier 2006, faisant suite à la réunion du jour précédent au cours de laquelle F._ avait exprimé des craintes quant à son avenir, les X._ ont déclaré qu'ils ne pouvaient absolument pas envisager un engagement de durée indéterminée. Au mieux, ils pourraient lui offrir une dernière prolongation jusqu'au 31 août 2007, sans garantie. Ils ont très vivement encouragé F._ à entreprendre rapidement des démarches pour trouver un emploi "à l'extérieur des X._". Cette lettre ayant suscité des difficultés d'interprétation, une entrevue a eu lieu le 9 février 2006 entre la responsable des ressources humaines, le directeur adjoint de la direction informatique, F._ et G._ (ancien collaborateur des X._ ayant travaillé dans le même service que ce dernier et ayant assuré la fonction de représentant syndical). Suite à cette séance, les X._ ont confirmé par courrier du 16 février 2006 que F._ pouvait effectuer des recherches d'emploi également au sein des X._, regrettant la confusion ainsi créée. Par courrier du 4 mai 2006, les X._ ont informé F._ que son contrat ne serait pas prolongé au-delà du 31 août 2006. Le 28 juin 2006, par l'entremise d'un avocat, F._ a demandé à être reçu par les X._. Il faisait valoir qu'il n'était pas acceptable que ceux-ci renvoient un collaborateur ayant donné satisfaction durant plus de cinq ans. Il avait abusivement été maintenu dans un statut d'auxiliaire, l'interruption durant l'été 2004 n'ayant eu d'autre but que de celui de l'empêcher de bénéficier d'un poste stable. Les X._ ont fait suite à cette requête le 7 juillet 2006, proposant une rencontre fin juillet ou début août 2006. Ils se contentaient de préciser que c'était à la demande expresse de F._ qu'un nouveau contrat de durée déterminée lui avait été proposé à partir du 1er septembre 2004. Le représentant syndical avait lui-même suggéré ce mode de faire, en s'engageant à ne pas le considérer comme liant les X._ à long terme. Par acte du 8 août 2006, F._ a recouru auprès du Tribunal administratif de la République et canton de Genève (ci-après: le Tribunal administratif) contre la résiliation de son contrat de travail, concluant à ce que le statut d'employé lui soit reconnu de même qu'à ce que la nullité, subsidiairement l'annulation, de son licenciement soit constatée. Par courrier du 4 octobre 2006, le juge délégué a demandé aux X._ de produire les documents suivants: demande de F._ de se voir proposer un engagement dès le 1er septembre 2004 et/ou compte rendu de la séance au cours de laquelle cette demande aurait été formulée; proposition de G._ de ne pas considérer ce mode de faire comme engageant les X._ sur le long terme et/ou compte rendu de la séance au cours de laquelle ce point aurait été évoqué; compte rendu de la séance du 9 février en présence de F._ et G._. Les X._ ont produit la lettre de candidature de F._ pour le poste auquel il a été engagé dès septembre 2004 ainsi que des courriers évoquant les réunions des 19 janvier et 9 février 2006. Ils précisaient qu'il n'existait pas de document écrit relatif à l'entretien qui s'était déroulé avec le représentant syndical. L'accord n'avait été qu'oral. Plusieurs témoins ont été entendus: G._, H._ (directeur adjoint de la direction informatique de gestion), I._ (directeur de la direction informatique de gestion), J._ (supérieure hiérarchique de F._), K._ (supérieur hiérarchique également), L._ (analyste-programmeur au sein du même groupe que G._ et F._) et enfin, M._ (membre de la délégation des syndicats du service public ayant négocié l'attribution de trois postes supplémentaires à l'informatique, qui devaient revenir aux collaborateurs n'étant pas au bénéfice d'un contrat de durée indéterminée). Le 15 mars 2007, F._ a complété ses conclusions du 8 août 2006, en ce sens qu'il soit constaté que le contrat du 17 août 2004 aurait dû être conclu sous forme d'un contrat de durée indéterminée et qu'il soit ordonné qu'il soit modifié en ce sens. Il contestait au surplus avoir été présent lors de la réunion au cours de laquelle G._ aurait prétendument pris l'engagement de ne pas "créer de problèmes". Par arrêt du 13 novembre 2007, le Tribunal administratif a admis, dans la mesure de sa recevabilité, le recours contre le courrier des X._ du 4 mai 2006 valant décision de résiliation des rapports de service et constaté la nullité de cette dernière. B. Agissant par la voie du recours en matière de droit public, les X._ demandent au Tribunal fédéral de constater que les rapports de travail conclus avec F._ ont pris fin le 31 août 2006. Subsidiairement, ils requièrent que l'arrêt rendu le 13 novembre 2007 par le Tribunal administratif soit annulé et que la cause soit renvoyée à cette autorité pour nouvelle décision dans le sens des considérants. Ils invoquent le principe de l'interdiction de l'arbitraire. Ils sollicitent en outre l'octroi de l'effet suspensif. Par ordonnance du 25 janvier 2008, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif des X._. Le Tribunal administratif n'a formulé aucune observation sur le recours. F._ a conclu à son rejet. 