Faits: A. A._ a été engagé auprès du service des établissements de détention (ci-après: SED) du département de justice, police et sécurité du canton de Genève (devenu le département des institutions) 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é à la "maison de Montfleury" 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 A._ puisse s'inscrire auprès de l'Institut d'études sociales de la haute école de travail social (ci-après: l'Institut) en vue d'une formation d'éducateur spécialisé qui lui permettrait d'être engagé à long terme au sein du SED. Par arrêté du Conseil d'Etat du 8 novembre 2006, A._ 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, A._ a signé un "contrat pédagogique tripartite" avec le directeur de Monfleury et un représentant de l'Institut. Ce contrat spécifiait que le taux d'activité de l'intéressé serait de 70 % pendant sa formation. A._ 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 SED. 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. Par arrêté du Conseil d'Etat du 17 décembre 2007 avec effet au 1er octobre 2007, A._ 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. B. A._ a recouru auprès du Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) contre cet arrêté de promotion. Il concluait principalement à ce que celui-ci soit annulé et que son traitement s'élève au 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. C. Par arrêt du 29 avril 2008, le Tribunal administratif a déclaré ce recours irrecevable. Il a estimé 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. D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler cet arrêt et de renvoyer la cause au Tribunal administratif pour instruction au fond et nouvelle décision dans le sens des considérants. Il se plaint d'une application arbitraire du droit cantonal (art. 9 Cst.) et d'une violation du principe de l'égalité de traitement (art. 8 Cst.). Il invoque également le droit d'avoir accès à un tribunal conformément aux art. 6 CEDH et 30 Cst. Il requiert en outre l'octroi de l'effet suspensif. Le Conseil d'Etat s'est déterminé; il conclut au rejet du recours. Le Tribunal administratif a renoncé à présenter des observations. E. Par ordonnance du 3 juillet 2008, le Président de la Ire Cour de droit public a rejeté la requête d'effet suspensif.