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.

Considérant en droit:
1. La décision attaquée a été rendue en matière de rapports de travail de droit public au sens de l'art. 83 let. g LTF. Le recourant cherche principalement à obtenir un traitement plus élevé ou le versement d'une indemnité correspondant à la perte de salaire pendant la durée de sa formation. Il s'agit donc d'une contestation de nature pécuniaire, de sorte que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. La valeur litigieuse atteint le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public dans ce domaine (art. 51 al. 2 et 85 al. 1 let. b LTF).
2. Dans son mémoire, le recourant évoque les art. 6 CEDH et 30 Cst. pour se plaindre du fait que sa cause n'a pas pu être soumise à un tribunal. S'il est vrai que le recourant se plaint principalement d'arbitraire, l'essentiel de son argumentaire peut néanmoins être rattaché au grief précité. On peut donc admettre que ce moyen répond aux exigences de motivation des art. 42 al. 2 et 106 al. 2 LTF (cf. <ref-ruling> consid. 1.4.2 p. 254; <ref-ruling> consid. 2.1. p. 31, 258 consid. 1.3 p. 261 s.; <ref-ruling> consid. 2.1 p. 120 et les références).
2.1 Le droit d'avoir accès à un tribunal est garanti non seulement par les art. 30 Cst. et 6 CEDH invoqués par le recourant, mais également par l'art. 29a Cst. En vigueur depuis le 1er janvier 2007, cette disposition donne à toute personne le droit à ce que sa cause soit jugée par une autorité judiciaire. La Confédération et les cantons peuvent, par la loi, exclure l'accès au juge dans des cas exceptionnels. Cette norme étend le contrôle judiciaire à toutes les matières, y compris aux actes de l'administration, en établissant une garantie générale de l'accès au juge (<ref-ruling> consid. 4.2 p. 327 et les références). Selon la jurisprudence, elle est concrétisée par l'<ref-law>, aux termes duquel les cantons doivent instituer des tribunaux supérieurs qui statuent comme autorités précédant immédiatement le Tribunal fédéral, sauf dans les cas où une autre loi fédérale prévoit qu'une décision d'une autre autorité judiciaire peut faire l'objet d'un recours devant le Tribunal fédéral. L'<ref-law> impartit aux cantons un délai de deux ans pour édicter les dispositions d'exécution y relatives. Avant l'expiration de ce délai, le grief lié à l'absence d'accès à un tribunal supérieur n'est en principe pas fondé (arrêts 2C_64/2007 du 29 mars 2007 consid. 3.2, 1D_3/2008 du 10 juillet 2008 consid. 3.2; Denise Brühl-Moser, in Basler Kommentar, Bundesgerichtsgesetz, 2008, n. 5 ad <ref-law>), de sorte que le recourant ne pourrait pas se prévaloir de l'art. 29a Cst. pour exiger que sa cause soit traitée par une telle autorité. En l'état, la présente cause doit par conséquent être examinée uniquement à la lumière des art. 6 CEDH et 30 Cst.
2.2 L'art. 6 par. 1 CEDH donne à toute personne le droit à ce que sa cause soit entendue équitablement, publiquement et dans un délai raisonnable, par un tribunal indépendant et impartial établi par la loi, qui décidera soit des contestations sur ses droits et obligations de caractère civil, soit du bien-fondé de toute accusation en matière pénale dirigée contre elle. Quant à l'art. 30 al. 1 Cst., il prévoit que toute personne dont la cause doit être jugée dans une procédure judiciaire a droit à ce que sa cause soit portée devant un tribunal établi par la loi, compétent, indépendant et impartial. Il faut entendre par tribunal un organe juridictionnel compétent pour résoudre un litige sur la base de normes juridiques à l'issue d'une procédure organisée. Il doit s'agir en outre d'une autorité dont l'indépendance, notamment à l'égard de l'exécutif et des parties, ainsi que l'impartialité, sont favorisées par des règles relatives au statut personnel de ses membres et à la procédure qu'elle doit suivre pour rendre ses décisions (<ref-ruling> consid. 2.2 p. 284; <ref-ruling> consid. 2a/bb p. 230 s.; ANDREAS AUER ET AL., Droit constitutionnel suisse, vol. II, 2e éd. 2006, p. 571).
2.3 La jurisprudence de la Cour européenne des droits de l'homme relative à l'art. 6 par. 1 CEDH a récemment étendu le champ d'application de cette disposition en ce qui concerne les employés publics. Elle s'est écartée de l'ancien "critère fonctionnel", selon lequel étaient soustraits au champ d'application de l'art. 6 par. 1 CEDH "les litiges des agents publics dont l'emploi était caractéristique des activités spécifiques de l'administration publique dans la mesure où celle-ci agit comme détentrice de la puissance publique chargée de la sauvegarde des intérêts généraux de l'Etat ou des autres collectivités publiques" (arrêt Pellegrin contre France du 8 décembre 1999, Recueil CourEDH 1999-VIII § 66). Désormais, il y a une présomption que l'art. 6 par. 1 CEDH s'applique dans les contestations relatives aux employés publics. Pour que ces litiges soient soustraits à la protection offerte par cette norme, deux conditions doivent être remplies. En premier lieu, le droit interne de l'Etat concerné doit avoir expressément exclu l'accès à un tribunal s'agissant du poste ou de la catégorie de salariés en question. En second lieu, cette dérogation doit reposer sur des motifs objectifs liés à l'intérêt de l'Etat. Le simple fait que l'intéressé relève d'un secteur ou d'un service qui participe à l'exercice de la puissance publique n'est pas en soi déterminant. Il faut encore que l'objet du litige soit lié à l'exercice de l'autorité étatique, de sorte que les conflits ordinaires du travail - tels ceux portant sur un salaire, une indemnité ou d'autres droits de ce type - ne sont en principe pas soustraits aux garanties de l'article 6 CEDH (arrêt Vilho Eskelinen et autres contre Finlande du 19 avril 2007, § 62).
2.4 En l'occurrence, les conditions posées par la jurisprudence susmentionnée pour soustraire un employé public à la protection offerte par l'art. 6 CEDH ne sont pas réunies. En effet, le droit applicable n'exclut pas expressément, pour des motifs qui seraient liés à l'intérêt de l'Etat, l'accès à un tribunal pour le poste du recourant ou pour la catégorie de salariés à laquelle il appartient. Or, le recourant s'est vu refuser l'accès au Tribunal administratif en vertu de dispositions cantonales de procédure, qui limitent cette voie de droit en matière de rapports de travail de droit public aux cas concernant une sanction disciplinaire, une résiliation des rapports de service ou un certificat de travail. Son recours a été déclaré irrecevable et n'a pas été transmis à une autre autorité judiciaire. De plus, il n'apparaît pas que sa cause puisse être examinée par un autre tribunal au niveau cantonal, le Tribunal administratif et le Conseil d'Etat ne soutenant d'ailleurs pas le contraire. Par ailleurs, sous l'angle de l'art. 6 par. 1 CEDH, le Tribunal fédéral ne saurait être la seule autorité judiciaire compétente pour connaître du litige. Son pouvoir d'examen est en effet fortement limité en ce qui concerne les faits de la cause, puisqu'il statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 et 118 al. 1 LTF). Il convient enfin de relever que, même si le législateur cantonal avait prévu une dérogation, l'objet du litige - à savoir le montant du salaire - est manifestement étranger à l'exercice de l'autorité étatique, de sorte qu'il n'y a pas de raison objective de soustraire cette cause aux garanties de l'art. 6 CEDH.
Dans ces conditions, il y a lieu de constater que la cause du recourant n'a pas été examinée par un tribunal, de sorte que l'art. 6 par. 1 CEDH a été violé. Il se justifie donc 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 posées par l'art. 30 al. 1 Cst.
3. Il s'ensuit que le recours doit être admis et l'arrêt attaqué annulé, l'affaire étant renvoyée au Tribunal administratif pour nouvelle décision dans le sens des considérants. Il n'y a pas lieu de percevoir des frais judiciaires (<ref-law>). Le recourant, assisté d'un avocat, a droit à des dépens, à la charge de l'Etat de Genève (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis; l'arrêt attaqué est annulé et la cause est renvoyée au Tribunal administratif du canton de Genève, pour nouvelle décision dans le sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Une indemnité de 2000 fr. est allouée au recourant à titre de dépens, à la charge de l'Etat de Genève.
4. Le présent arrêt est communiqué au mandataire du recourant, ainsi qu'au Conseil d'Etat et au Tribunal administratif du canton de Genève.
Lausanne, le 27 octobre 2008
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener