Faits:
A. L'Aéroport international de Genève (ci-après: l'AIG) a engagé G._ en qualité de X._ 1 au mois de février 1996. Celui-ci a été nommé X._ 2 en décembre 1998. Depuis le 1er janvier 2009, G._ a travaillé à la section Y._ de la division Z._.
Le 26 janvier 2005, G._ a été victime d'un accident professionnel qui l'a rendu incapable de travailler jusqu'au 7 avril 2005. Il s'est à nouveau retrouvé en arrêt de travail pour cause de maladie du 28 mars au 2 juillet 2006.
Le 16 septembre 2006, l'intéressé s'est rendu à V._, à l'étranger, pour participer à un cours d'entraînement intensif d'une semaine. A son arrivée, il a présenté un certificat médical attestant une indisposition à porter de lourdes charges. En raison des exigences de sécurité très strictes prévalant dans cette école, sa participation a été refusée et il a été prié de rentrer chez lui. A la suite de cet incident, la Direction générale de l'AIG a reproché à G._ de ne pas avoir informé ses supérieurs hiérarchiques au sujet de son état de santé préalablement à son départ pour V._. Son comportement constituait une faute professionnelle, dès lors qu'il avait engendré des coûts inutiles et privé une autre personne de cette formation. L'intéressé a contesté les reproches formulés à son égard.
G._ a été en incapacité de travail les 9 et 10 février 2007, en raison d'une grippe. Le 16 février suivant, il a reçu une lettre de sa hiérarchie le priant de lui fournir un certificat médical pour cette absence de deux jours. A cette occasion, il lui a été rappelé que s'il ne pouvait pas prendre son service pour des raisons de maladie, il devait avertir son responsable hiérarchique avant l'heure planifiée de sa prise de service, afin que son remplacement puisse être assuré dans les meilleurs délais. En outre, il devait présenter jusqu'à nouvel avis un certificat médical dès le premier jour d'absence. A défaut, des mesures plus coercitives seraient prises à son encontre, pouvant aller jusqu'à la résiliation des rapports de service. G._ a répondu le 24 février 2007.
Le 9 mai 2008, M._ (représentant du syndicat des services publics) a écrit au directeur de l'AIG, lui demandant que les pressions exercées sur G._ cessent immédiatement et que les accusations dont ce dernier avait fait l'objet dans plusieurs courriers soient officiellement annulées par écrit. L'AIG a contesté le fait que G._ fût soumis à de quelconques pressions et a informé le syndicat qu'il ne souhaitait plus entrer en matière sur les faits invoqués.
Au cours d'une réunion ayant eu lieu le 16 mars 2009 avec la Direction générale de l'AIG, G._, assisté de M._ et de son conseil, a exposé son souhait qu'une «décision» soit rendue au sujet des avertissements reçus entre 2006 et 2007. L'AIG a pour sa part indiqué que ceux-ci avaient déjà fait l'objet de plusieurs échanges de courriers, de sorte qu'elle n'entendait plus y revenir. La question de la fin des rapports de travail et la proposition de l'AIG de négocier une convention de départ a ensuite été abordée. A l'évocation de cette dernière éventualité, G._ a été pris d'un malaise et la discussion n'a pas pu se poursuivre. Depuis cette date, G._ s'est trouvé en incapacité de travail. Par courrier du 20 mars 2009, l'AIG a confirmé sa proposition de mettre un terme conventionnel aux rapports de travail.
Le 26 mars 2009, G._ a contesté l'existence d'un conflit relationnel avec ses supérieurs hiérarchiques. Il a par ailleurs sollicité l'ouverture d'une enquête interne en application de l'art. 9 du Règlement sur la protection de la personnalité de l'AIG. Le 25 septembre 2009, l'AIG a ordonné l'ouverture d'une enquête interne et confié celle-ci à P._, président de la Cour de justice. Celui-ci a débuté son enquête par l'audition des témoins D._, R._, S._ et A._ le 9 décembre 2009.
Le 11 décembre 2009, G._ a informé l'AIG qu'il reprendrait son travail à plein temps à partir du 4 janvier 2010.
Par décision du 21 décembre 2009, l'AIG a licencié G._ avec effet au 30 juin 2010, tout en le libérant de l'obligation de travailler dès le 1er janvier 2010.
G._ a recouru contre son licenciement devant la commission de recours de l'AIG. Après avoir procédé à l'audition des parties ainsi que de plusieurs témoins par audiences de comparution personnelle des 21 mai et 2 juillet 2010, la commission de recours de l'AIG a rejeté le recours de G._ par décision du 15 septembre 2010.
B. G._ a recouru contre cette décision devant le Tribunal administratif (depuis le 1er janvier 2011: Chambre administrative de la Cour de justice). Il a sollicité l'annulation de la décision attaquée et sa réintégration ou, à défaut, le paiement d'une indemnité équivalente à dix-huit mois de salaire fixe, soit un montant de 138'159 fr. 90, avec intérêts à 5 % à compter du 30 juin 2010.
Par jugement du 5 avril 2011, la juridiction cantonale a annulé la décision de licenciement et proposé la réintégration de G._. Elle a en outre ordonné à l'AIG, en cas de refus de procéder à la réintégration, de lui transmettre sa décision pour fixation d'une indemnité.
C. L'AIG a formé un recours en matière de droit public dans lequel il a conclu, principalement, à l'annulation de l'arrêt attaqué et à la confirmation du licenciement prononcé le 21 décembre 2009. Subsidiairement, il a conclu au renvoi de la cause à la juridiction cantonale pour nouvelle décision dans le sens des considérants.
G._ conclut au rejet du recours.
D. Par ordonnance du 14 septembre 2011, le juge instructeur a accordé l'effet suspensif au recours.

Considérant en droit:
1. 1.1 L'AIG est un établissement de droit public autonome jouissant de la personnalité juridique. Il est organisé selon la loi cantonale genevoise sur l'Aéroport International de Genève du 10 juin 1993 (LAIG; RS-GE H 3 25). Selon l'art. 4 du statut du personnel de l'AIG (ci-après: le statut), tous les membres du personnel sont liés à l'AIG par des rapports de droit public.
1.2 Selon l'art. 83 let. g LTF, en matière de rapports de travail de droit public (lorsque, comme en l'espèce, la question de l'égalité des sexes n'est pas en cause), le recours en matière de droit public est irrecevable contre les décisions qui concernent une contestation non pécuniaire. Il ressort du dossier que l'intimé conclut principalement à l'annulation de la décision résiliant ses rapports de service et, subsidiairement, au versement d'une somme d'argent. Dans cette mesure, il s'agit d'une contestation pécuniaire, et le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération (voir les arrêts 8C_170/2009 du 25 août 2009 consid. 1.1; 1C_547/2008 du 23 février 2009 consid. 2.1 et 1C_116/ 2007 du 24 septembre 2007 consid. 2). En outre, le seuil requis de la valeur litigieuse (art. 85 al. 1 let. b LTF) est atteint (cf. p. ex arrêt 8C_541/2010 du 20 juin 2011 consid. 1.2).
2. Le recours en matière de droit public (art. 82 ss LTF) peut être formé pour violation du droit selon l'art. 95 sv. LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Il statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF) et peut rectifier ou compléter d'office les constatations de celle-ci si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF). Le recourant qui entend s'écarter des faits constatés doit expliquer de manière circonstanciée en quoi les conditions de l'art. 105 al. 2 LTF sont réalisées sinon un état de fait divergent ne peut pas être pris en considération.
3. Sous le chapitre «Durée et fin des rapports de service» et le titre marginal «Procédure et justification», l'art. 57 du statut dispose ce qui suit:
A) Cadres supérieurs, cadres et employés
1 Avant de notifier une résiliation, l'AIG doit entendre l'intéressé. Si l'intéressé ne peut ou ne veut être entendu, l'AIG lui notifie la résiliation par écrit sans l'avoir entendu au préalable.
2 La lettre de résiliation doit contenir les motifs de celle-ci et mentionner expressément que l'intéressé dispose d'un délai de trente jours pour recourir contre la décision.
3 L'AIG ne peut notifier une résiliation que pour un motif justifié. Cette condition est remplie lorsque, pour une raison sérieuse, la poursuite des rapports de travail n'est pas dans l'intérêt du bon fonctionnement du service.
4 Lorsque le motif justifié résulte de prestations devenues insuffisantes pour des raisons de santé, l'article 58 al. 2 du statut est applicable par analogie si l'intéressé a vingt ans d'ancienneté et ne reçoit pas une rente complète de l'assurance-invalidité ou de la CIA.
5 Lorsqu'un licenciement est déclaré injustifié par l'autorité de recours, cette dernière peut proposer la réintégration de l'intéressé et, en cas de refus de l'AIG, condamner celui-ci au paiement d'une indemnité ne dépassant pas dix-huit mois de salaire fixe.
6 (...)
L'AIG a adopté un règlement sur la protection de la personnalité le 14 mai 2004 (ci-après: le règlement). Celui-ci prévoit à son art. 9 (dans sa version du 13 juillet 2009) que l'AIG peut, sur demande de la personne s'estimant lésée, décider d'ouvrir une enquête interne (al. 1). Dans ce cas, l'AIG, par l'entremise de la division des ressources humaines, désigne une personne ou plusieurs personne(s) externe(s) à l'AIG pour mener une enquête (al. 2). Afin d'assurer le bon déroulement de l'enquête, l'AIG s'engage notamment à n'exercer aucune représailles à l'égard des personnes s'estimant lésées et des témoins (al. 5 let. c). En relation avec ces dispositions et sous le titre marginal «Code de conduite», l'art. 6 al. 1 dudit règlement prévoit qu'aux fins de parvenir aux buts fixés par le règlement, la direction générale veille à ne pas licencier de ce fait les personnes qui auront porté plainte de bonne foi, ni les déplacer contre leur gré et ce, pendant tout la durée de la procédure (let. c).
4. En substance, les premiers juges ont admis l'existence d'un lien de causalité entre les plaintes pour mobbing de l'intimé et son licenciement. Ils ont retenu qu'en licenciant l'intimé pendant la procédure d'enquête, l'AIG avait contrevenu à l'art. 6 al. 1 let. c du règlement. Par ailleurs, l'existence d'un motif justifié de licenciement au sens de l'art. 57 (A) al. 3 du statut, ne pouvait être reconnu avant que l'enquête n'ait été menée à son terme et qu'un rapport, infirmant ou confirmant le bien-fondé des plaintes du recourant, n'ait été dressé. Le licenciement était donc injustifié. Aussi bien la juridiction cantonale a-t-elle proposé la réintégration de l'intimé. En cas de refus de l'AIG, celui-ci devait transmettre sa décision à la chambre administrative pour qu'elle fixe le montant de l'indemnité en application de l'art. 57 (A) al. 5 du statut.
5. Le recourant se plaint à divers titres d'arbitraire dans l'appréciation des preuves et l'établissement des faits (art. 9 Cst.).
Tout d'abord, les premiers juges auraient retenu de manière insoutenable l'existence d'un lien de causalité entre la demande d'ouverture d'une enquête interne par l'intimé et son congé. Deuxièmement, le recourant estime qu'une appréciation des preuves dénuée d'arbitraire aurait dû conduire la cour cantonale à retenir que le licenciement était la conséquence d'une part, d'un conflit relationnel persistant entre l'intimé et sa hiérarchie et, d'autre part, des longues absences de l'intimé, lesquelles nuisaient à la qualité de son travail et au bon fonctionnement du service.
6. Dans le domaine de l'appréciation des preuves et de la constatation des faits, le Tribunal fédéral se montre toutefois réservé, vu le large pouvoir qu'il reconnaît en la matière à l'autorité cantonale (<ref-ruling> consid. 4b p. 40; <ref-ruling> consid. 1b p. 30 et les références citées). Il n'intervient, du chef de l'art. 9 Cst., que si le juge du fait n'a manifestement pas compris le sens et la portée d'un moyen de preuve, a omis sans motifs objectifs de tenir compte de preuves pertinentes ou a opéré, sur la base des éléments recueillis, des déductions insoutenables (<ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 2.1 p. 9).
6.1 Les premiers juges ont retenu que le fait de prononcer le licenciement peu après l'ouverture de l'enquête interne, juste après l'audition de témoins favorables à l'intimé, plaidait en faveur d'un lien de causalité entre les plaintes de l'intimé et son licenciement. Ils ont en outre considéré que l'existence de ce lien était d'autant plus crédible au regard des motifs de licenciement avancés.
6.2 La question de savoir s'il existe un lien de causalité entre les plaintes de l'intimé et le licenciement prononcé par le recourant, de même que les motifs de licenciement, relèvent du fait, de sorte que les constatations de la cour cantonale y relatives lient le Tribunal fédéral, qui ne peut s'en écarter que si elles ont été établies de façon manifestement inexacte ou en violation du droit (cf. consid. 2).
Le fait que le recourant a accepté d'ouvrir une enquête interne à la demande de l'intimé montre qu'il accordait un certain crédit aux plaintes de celui-ci. Il est exact d'autre part que les premiers témoignages recueillis pouvaient donner à penser que l'enquête prenait une tournure défavorable au recourant (voir en particulier les témoignages de R._ et S._). On peut donc penser que l'employeur a voulu couper court à toute discussion et précipiter les choses en licenciant l'intimé avant que l'enquête n'aille à son terme et après avoir constaté que l'intéressé entendait reprendre le travail après une période d'incapacité de travail. On note par ailleurs que les faits invoqués à l'appui du licenciement étaient antérieurs à l'enquête. Le licenciement n'est pas motivé par un fait nouveau imputable à l'intimé et qui serait postérieur à la décision d'ouvrir une enquête. S'agissant des motifs de licenciement, les premiers juges constatent qu'en dehors de la défiance invoquée - intimement liée «aux prétentions de mobbing» de l'intimé -, la prétendue inaptitude physique de l'intéressé n'était appuyée par aucun élément objectif. Concernant les suites physiques de l'accident de 2005, elles n'avaient entraîné aucune inaptitude au dire du médecin-conseil et des deux derniers supérieurs hiérarchiques de l'intéressé. Quant au motif d'arrêt de travail pour cause de maladie, il était exclusivement d'ordre psychique et directement lié au conflit avec la hiérarchie.
Sur la base de ces éléments, la constatation des premiers juges quant à l'existence d'un lien causal entre la plainte de l'intimé, en fonction de la tournure des auditions, et le licenciement échappent au grief d'arbitraire.
7. Invoquant une violation de son droit d'être entendu (art. 29 al. 2 Cst.), le recourant soutient que, dès lors qu'il y avait des motifs de congé (conflit relationnel et longues absences qui nuisaient à la qualité du travail), les juges cantonaux auraient dû déterminer si les rapports de service auraient tout de même pu être résiliés pour ces motifs. Il convenait de vérifier si ces motifs étaient à même de rompre le prétendu lien de causalité entre le «mobbing allégué et le licenciement».
De manière analogue à un licenciement abusif, s'il n'est pas nécessaire que les prétentions émises par le travailleur aient été seules à l'origine de la résiliation, il doit s'agir néanmoins du motif déterminant. En d'autres termes, ce motif doit avoir essentiellement influencé la décision de l'employeur de licencier; il faut ainsi un rapport de causalité entre les prétentions émises et le congé signifié au salarié (arrêts 4C.84/2005 du 16 juin 2005 consid. 3.1; 4C.27/1992 du 30 juin 1992 in SJ 1993 p. 360, consid. 3a). L'incidence respective des divers motifs de résiliation en concours est une question qui relève de la causalité naturelle (<ref-ruling> consid. 4.1 p. 702). En l'espèce, comme on l'a vu, les premiers juges ont constaté sur la base d'indices sérieux que la plainte de l'intimé était en relation avec le licenciement. Ils sont parvenus à la conclusion que l'existence d'un motif justifié de licenciement ne pouvait être reconnu avant que l'enquête n'eût été menée à son terme et qu'un rapport infirmant ou confirmant le bien-fondé des plaintes formulées n'eût été dressé. Dans ce contexte, on ne voit pas que le droit d'être entendu du recourant ait été violé ni que les premiers juges aient fait une application arbitraire de la réglementation en cause. On ne peut en tout cas pas dire que la décision de licencier l'intimé était déjà prise avant la décision de mettre sur pied une enquête ou qu'il existait déjà à ce moment des motifs de licenciement suffisamment établis. Si tel avait le cas, il n'y aurait eu aucun sens pour l'employeur d'ordonner une enquête interne, dont le but était précisément d'établir les faits et d'établir un rapport d'enquête à l'attention de l'AIG avec des recommandations concernant toutes les mesures utiles pour résoudre le conflit et rétablir un climat de confiance (cf. art. 9 du règlement).
8. 8.1 Le recourant considère que l'interprétation donnée par la juridiction cantonale de l'art. 6 al. 1 let. c du règlement est arbitraire car elle obligerait l'AIG, dans tous les cas, à attendre l'issue de la procédure d'enquête interne avant de pouvoir justifier un licenciement. Une telle interprétation serait contraire aux buts du règlement, lequel vise à assurer la protection des employés contre les atteintes à leur personnalité mais non à leur conférer une protection absolue contre le licenciement. Si tel était le cas, il suffirait à toute personne de demander l'ouverture d'une enquête pour bloquer un congé en soi admissible.
8.2 Le fait que le recourant a accédé à la demande de l'intimé d'ouvrir une procédure d'enquête montre qu'il ne considérait pas ses griefs de mobbing comme imaginaires ni que ceux-ci eussent été allégués abusivement. En ordonnant l'ouverture d'une enquête interne, l'employeur a signalé qu'il appartenait désormais à l'enquêteur de faire toute la lumière sur les circonstances qui avaient conduit à une détérioration des relations entre l'employé et ses supérieurs et, en particulier, sur les actes de mobbing invoqués par l'intimé. En pareilles circonstances, l'employeur ne saurait, sous peine de contrevenir de manière caractéristique au principe de la bonne foi, licencier l'employé dès le début de l'enquête et sans que des éléments nouveaux puissent être invoqués à la charge de celui-ci.
8.3 C'est donc sans arbitraire que la juridiction cantonale a retenu que le licenciement de l'intimé pendant la procédure d'enquête était injustifié et qu'il convenait en conséquence de faire application de l'art. 57 (A) al. 5 du statut.
9. Vu l'issue du litige, les frais de justice doivent être supportés par le recourant, qui succombe (art. 66 al. 1, première phrase, LTF). Celui-ci versera également une indemnité à l'intimé à titre de dépens (art. 68 al. 1 LTF).

Le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimé une indemnité de 2'800 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lucerne, le 12 avril 2012
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
La Greffière: Fretz Perrin