Faits: Faits: A. A.a Ressortissant italien, B.X._ est arrivé le 30 mars 1992 à Genève pour travailler au Consulat général d'Italie (ci-après: le Consulat). Sa femme, A.X._, l'a rejoint le 1er juillet 1992. Les époux X._ ont cinq enfants nés entre 1980 et 1986, qui habitent avec eux en Suisse depuis 1992. B.X._ a acquis la nationalité suisse le 16 mars 2001. Les époux X._ - qui avaient déjà requis des allocations familiales le 30 novembre 1992 - ont demandé, à partir de 1995, des allocations d'études en faveur de leurs enfants sur la base de la loi genevoise du 4 octobre 1989 sur l'encouragement aux études (ci-après: la loi cantonale ou LEE) et ils ont d'abord essuyé un refus. Toutefois, le 7 mai 2002, le Service des allocations d'études et d'apprentissage du canton de Genève (ci-après: le Service cantonal) a mis les enfants X._ au bénéfice d'allocations d'études dès l'année scolaire 2000-2001. En revanche, par décision du 17 février 2003, le Service cantonal a refusé le remboursement rétroactif des taxes scolaires déjà perçues. Il a confirmé cette décision le 29 avril 2003, puis le 13 août 2003. A.b Les époux X._ ont alors porté leur cause devant le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif). Ils ont conclu à l'annulation de la décision du Service cantonal du 13 août 2003 ainsi qu'à la constatation de leur droit de recevoir des allocations d'études et d'être exemptés des taxes scolaires pour leurs enfants en ce qui concernait les années scolaires 1995-1996 à 1999-2000. Ils ont notamment allégué devoir être imposés comme contribuables dans le canton de Genève selon la convention du 9 mars 1976 entre la Confédération suisse et la République italienne en vue d'éviter les doubles impositions et de régler certaines autres questions en matière d'impôts sur le revenu et sur la fortune (ci-après: la Convention italo-suisse ou CDI-I; RS 0.672.945.41), le revenu provenant du travail de B.X._ au Consulat étant imposé à la source en Italie. Dans son arrêt du 16 août 2005, le Tribunal administratif a décrit la situation fiscale des époux X._ à partir des renseignements fournis par l'Administration fiscale cantonale genevoise (ci-après: l'Administration fiscale). B.X._ avait bénéficié d'un permis "exempt" du 11 mai 1992 au 27 juin 2001 en raison de sa fonction au Consulat. Les déclarations d'impôt des époux X._ mentionnaient que B.X._ était employé du Consulat et qu'il entendait se prévaloir de l'exemption de l'impôt sur le revenu, aucun revenu provenant de l'activité lucrative réalisée auprès du Consulat n'étant déclaré. Les taxations des intéressés avaient été établies selon les procédures prévues pour les personnes exonérées d'impôts, plus précisément pour les fonctionnaires internationaux. S'agissant de la taxation 2000, les époux X._ avaient demandé d'être mis au bénéfice de la Convention italo-suisse et mentionné, dans une nouvelle déclaration d'impôt, le revenu réalisé en 1999 par B.X._ auprès du Consulat. L'Administration fiscale avait admis cette nouvelle déclaration et avait alors appliqué la Convention italo-suisse aux intéressés, mais elle n'avait pas rouvert les taxations antérieures. En outre, il était établi que l'impôt à la source avait été prélevé en Italie sur le salaire versé par le Consulat. Sur cette base, le Tribunal administratif a considéré que, jusqu'à l'année fiscale 2000, les époux X._ n'avaient pas payé d'impôts sur la totalité de leurs revenus et n'avaient dès lors pas droit aux allocations d'études ni au remboursement des taxes scolaires déjà versées (cf. art. 2 lettre c LEE). En revanche, la taxation 2000, effectuée selon le système praenumerando, avait été fondée sur le revenu réalisé en 1999 auprès du Consulat. Il existait dès lors un droit aux allocations d'études et au remboursement des taxes scolaires à partir du 1er janvier 1999, et non pas seulement à partir de l'année scolaire 2000-2001. Le Tribunal administratif a admis le recours dans cette mesure et renvoyé la cause au Service cantonal pour qu'il fixe et alloue les montants dus. A.c Par arrêt du 29 septembre 2005, le Tribunal fédéral a déclaré irrecevable le recours de droit public formé contre l'arrêt du Tribunal administratif du 16 août 2005, dès lors que celui-ci ne constituait pas une décision finale. A.c Par arrêt du 29 septembre 2005, le Tribunal fédéral a déclaré irrecevable le recours de droit public formé contre l'arrêt du Tribunal administratif du 16 août 2005, dès lors que celui-ci ne constituait pas une décision finale. B. B.a Par courrier du 20 octobre 2005, les époux X._ ont demandé au Service cantonal de se prononcer, par une décision formelle, sur le versement d'allocations d'études et le remboursement de taxes scolaires à partir de l'année scolaire 1995-1996. Le 17 novembre 2005, le Service cantonal a répondu que les prestations dues en vertu de l'arrêt du Tribunal administratif du 16 août 2005 avaient été effectuées et qu'il ne pouvait pas accéder à la demande relative à des prestations pour les années scolaires "1995-96 et 1996-97", en raison de la teneur de l'arrêt précité. B.b Par arrêt du 28 mars 2006, le Tribunal administratif a déclaré irrecevable le recours interjeté par les époux X._ contre le courrier du Service cantonal du 17 novembre 2005, en précisant que l'acte des intéressés était irrecevable même en tant que demande de révision de son arrêt du 16 août 2005. B.b Par arrêt du 28 mars 2006, le Tribunal administratif a déclaré irrecevable le recours interjeté par les époux X._ contre le courrier du Service cantonal du 17 novembre 2005, en précisant que l'acte des intéressés était irrecevable même en tant que demande de révision de son arrêt du 16 août 2005. C. Agissant par la voie du recours de droit public, A.X._ et B.X._ demandent au Tribunal fédéral, sous suite de dépens, d'annuler l'arrêt du Tribunal administratif du 28 mars 2006. Ils se plaignent en substance d'arbitraire (cf. art. 9 Cst.). Ils reprochent au Tribunal administratif d'avoir retenu que la Convention italo-suisse ne s'appliquait pas à B.X._ pour les taxations 1997, 1998 et 1999, dans son arrêt du 16 août 2005, confirmé par son arrêt du 28 mars 2006. Ils lui font aussi grief d'avoir considéré que leur situation juridique avait changé le 1er janvier 1999, date déterminante pour la taxation 2000. Le Tribunal administratif a déclaré n'avoir aucune observation à formuler sur le recours. Le Service cantonal a fait sienne la réponse de l'autorité intimée.