Faits: A. A.a C._ a été engagé auprès du Service X._ du département V._ du canton de Genève en qualité d'auxiliaire «commis administratif 4», en classe 10/00 et à un taux d'activité de 100 % du 17 au 28 février 2003. Il a été affecté à Y._ en tant qu'éducateur non diplômé. Cet engagement a été plusieurs fois reconduit, puis prolongé à titre exceptionnel jusqu'au 31 octobre 2006, pour que C._ puisse s'inscrire auprès de l'Institut A._ de l'Ecole B._ en vue d'une formation d'éducateur spécialisé qui lui permettrait d'être engagé à long terme au sein du Service X._. Entre septembre 2003 et juin 2004, l'intéressé a suivi des cours du soir auprès de l'Ecole G._ et a passé avec succès les examens correspondants, de telle sorte qu'il remplissait, à la rentrée 2005, les conditions d'admission à l'Institut A._. Cependant, pour des raisons liées à l'organisation du service, l'entrée en formation a été différée. Par arrêté du Conseil d'Etat du 8 novembre 2006, C._ a été nommé fonctionnaire dès le 1er novembre 2006 en tant que «commis administratif 4», classe 11/02, avec les mêmes affectations et taux d'activité que précédemment. Le 3 août 2007, C._ a signé un «contrat pédagogique tripartite» avec le directeur de Y._ et un représentant de l'Institut A._. Ce contrat spécifiait que le taux d'activité de l'intéressé serait de 70 % pendant sa formation. Celle-ci s'étendait sur quatre années, à raison de deux jours de cours par semaine. Le 27 août 2007, l'Institut A._ a confirmé au directeur de Y._ que l'intéressé commencerait sa formation le 17 septembre 2007 en précisant que son taux d'activité durant cette période serait de 70 %. Le 27 août 2007, l'Institut A._ a confirmé au directeur de Y._ que l'intéressé commencerait sa formation le 17 septembre 2007 en précisant que son taux d'activité durant cette période serait de 70 %. A.b C._ s'est plaint de cette réduction de son taux d'activité auprès de l'Office du personnel de l'Etat de Genève et du directeur du Service X._. Il lui a été répondu, en substance, que la formation continue en vue d'un perfectionnement utile à la fonction devait être effectuée durant le temps libre et que d'autres collaborateurs qui avaient suivi un cursus identique au sien étaient dans la même situation. A.c Par arrêté du Conseil d'Etat du 17 décembre 2007 avec effet au 1er octobre 2007, C._ a été promu à la fonction de «commis administratif 5», classe 13/02, avec la même affectation que précédemment mais à un taux d'activité de 70 %. Il s'ensuivait une baisse de ses revenus mensuels de 1'288 fr. 80. A.d C._ a recouru auprès du Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif; depuis le 1er janvier 2011: Chambre administrative de la Cour de justice du canton de Genève) contre cet arrêté de promotion. Il concluait principalement à ce que celui-ci soit annulé et que son traitement corresponde à 100 % de la classe 13/02 dès le 1er octobre 2007, subsidiairement à sa réintégration à 100 % en qualité de commis administratif 4 en classe 11/03 depuis le 1er octobre. A défaut d'acceptation, l'Etat de Genève devrait être condamné à lui verser une indemnité de 76'949 fr. 80 correspondant à la perte de salaire durant les quatre années de formation. Il faisait valoir qu'il ignorait, lors de son engagement, qu'il subirait une réduction de salaire pendant cette période, qu'aucune disposition légale ne prévoyait la réduction unilatérale du traitement dans un tel cas et que plusieurs de ses collègues avaient pu suivre le même enseignement en cours d'emploi sans diminution de revenu. A.e Par jugement du 29 avril 2008, le Tribunal administratif a déclaré son recours irrecevable. Il a considéré que la décision du Conseil d'Etat du 17 décembre 2007 ne pouvait pas être assimilée à une résiliation des rapports de service, dès lors qu'il s'agissait d'un arrêté de promotion nommant l'intéressé à un poste rémunéré en classe 13, soit deux de plus que celui de commis administratif 4, avec une diminution du taux d'activité acceptée le 3 août 2007 lors de la signature du contrat pédagogique. Il a également jugé que la prétention du recourant visant à obtenir une indemnité devant compenser la diminution de 30 % du traitement pendant les quatre années de formation était directement liée au recours, si bien que celui-ci devait être déclaré irrecevable même s'il était considéré comme une action pécuniaire. A.f Par arrêt du 27 octobre 2008 (1_C 267/2008), le Tribunal fédéral a admis le recours formé par l'intéressé contre ce jugement. Il a constaté que la cause n'avait pas été examinée par un tribunal, de sorte que l'art. 6 par. 1 CEDH avait été violé. Il se justifiait, en conséquence, de renvoyer l'affaire au Tribunal administratif pour qu'il statue sur le fond du litige ou qu'il transmette la cause à une autre autorité judiciaire répondant aux exigences de l'art. 30 al. 1 Cst. B. A la suite de cet arrêt, le Tribunal administratif a repris l'instruction de l'affaire. Les parties se sont déterminées. Le tribunal a procédé à l'audition de nombreux témoins. Statuant le 31 août 2010, il a rejeté le recours. C. Agissant par la voie du recours en matière de droit public, C._ demande au Tribunal fédéral d'annuler ce jugement, ainsi que l'arrêté du Conseil d'Etat du 17 décembre 2007, et de dire que son traitement doit s'élever à 100 % de la classe 13/02 de l'échelle des traitements dès le 1er octobre 2007, annuités à suivre. Subsidiairement, il conclut au renvoi de la cause au Tribunal administratif en lui enjoignant de proposer au Conseil d'Etat sa réintégration à 100 % à la fonction de commis administratif 4 - 5 10 004 - cl. max. 11 à Y._, classe 11/03 de l'échelle du traitement à dater du 1er octobre 2007, annuités et promotions à suivre. A défaut d'acceptation, il conclut à la condamnation de l'Etat de Genève à lui verser une indemnité de 76'949 fr. 80. Plus subsidiairement, il conclut au renvoi de la cause au Tribunal administratif pour nouvelle décision au sens des motifs. Le Conseil d'Etat conclut au rejet du recours. 