Faits: A. Les époux X._ et Dame X._ (ci-après: les contribuables), précédemment domiciliés à Genève, ont transféré leur domicile en Valais avec effet au 1er octobre 2006. Le 18 février 2008, le Service cantonal des contributions du canton du Valais (ci-après: le Service cantonal) a arrêté le montant des acomptes provisionnels pour les impôts cantonaux 2008 à 0.- fr., selon le calcul suivant: - Montant présumé: 2'000.- - Impôt anticipé supputé: - 2'000.- Total: 0.-. Le 15 avril 2009, les contribuables ont procédé au versement d'un montant de 364'750.- fr. en prévision des impôts cantonaux pour l'année 2008. Le 16 mars 2010, le Service cantonal a notifié une décision de taxation en matière d'impôts cantonaux et communaux et d'impôt fédéral direct pour l'année 2008. S'agissant des impôts cantonaux, cette taxation retenait les éléments suivants: Total des impôts 1'371'130.-- Acomptes facturés 2'000.-- Différence (acomptes/bordereau) 1'369'130.-- Intérêt compensatoire négatif 28'557.10 Impôt anticipé 1'912'470.35 Paiement effectué 364'750.-- Intérêt rémunératoire 2'383.15 Solde en faveur des contribuables 879'916.40 L'intérêt compensatoire négatif a été calculé à partir de l'échéance générale valant pour les impôts cantonaux 2008, à savoir le 31 mars 2009. Pour déterminer le montant des intérêts, le Service cantonal a déduit du montant d'impôt dû selon la taxation, soit 1'371'130 fr., le 80% du montant de l'impôt anticipé 2005, à savoir 479'700 fr. La "base de calcul initiale" a ainsi été ramenée à 891'430 fr. B. Par écriture du 31 mars 2010, les contribuables ont contesté le prélèvement d'un intérêt compensatoire négatif de 28'557.10 fr. Le 11 mai 2010, le Service cantonal a réaffirmé le principe de l'intérêt compensatoire négatif, mais en a corrigé le calcul pour ramener le montant des intérêts exigés à 15'260.05 fr., tenant compte du versement de 364'750 fr. effectué le 15 avril 2009. Après échange de courriers, le Service cantonal a, par décision sur réclamation du 7 juin 2010, confirmé, par courrier du 7 juin 2010, la rectification du bordereau. C. Les contribuables ont introduit un recours contre cette décision auprès de la Commission de recours en matière fiscale du canton du Valais (ci-après: la Commission cantonale) par acte du 13 août 2010, concluant à son annulation et à la correction du bordereau dans le sens de la suppression de tout intérêt compensatoire négatif. La Commission cantonale a rejeté ce recours par décision du 21 septembre 2011, notifiée le 17 octobre 2011. Elle a motivé sa décision par l'application par analogie de l'art. 9 de l'arrêté cantonal relatif à la perception des impôts cantonaux et communaux par acomptes du 26 août 1992 (ci-après: l'arrêté cantonal; RS/VS 642.106) au calcul de l'intérêt moratoire courant dès l'échéance générale de l'impôt. D. Par acte du 17 novembre 2011, les contribuables ont interjeté un recours en matière de droit public auprès du Tribunal fédéral. A l'appui de leur recours, ils invoquent principalement la violation des principes de la légalité et de l'interdiction de l'arbitraire. La Commission cantonale et l'Administration fédérale des contributions ont renoncé à formuler des observations. Le Service cantonal conclut pour sa part au rejet du recours.