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.

Considérant en droit:
1. 1.1 Les recourants contestent la prétention de l'Etat du Valais au paiement d'un intérêt compensatoire négatif figurant sur l'avis de taxation ordinaire des impôts cantonaux 2008. Comme ce domaine relève du droit public et qu'aucune des exceptions prévues à l'<ref-law> n'est réalisée, la voie du recours en matière de droit public est en principe ouverte en vertu de l'<ref-law>.
1.2 Le recours est dirigé contre une décision finale (cf. <ref-law>) rendue par un tribunal supérieur statuant en dernière instance cantonale (cf. art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (<ref-law>) ne tombant pas sous le coup de l'une des exceptions prévues à l'<ref-law>. La voie du recours en matière de droit public est partant ouverte. L'art. 73 de la loi fédérale du 14 décembre 1990 sur l'harmonisation des impôts directs des cantons et des communes (LHID; RS 642.14) confirme cette voie de droit, dès lors que le recours concerne l'imposition sur le revenu, soit une matière harmonisée dont le principe figure à l'art. 7 de ladite loi. Déposé en temps utile (cf. <ref-law>) par les recourants qui ont un intérêt digne de protection à son annulation ou à sa modification (cf. art. 89 al. 1 let. b et c LTF), il est en principe recevable.
1.3 Le Tribunal fédéral examine librement si le droit cantonal et son interprétation par les autorités cantonales respectent les exigences de la loi sur l'harmonisation fiscale. Toutefois, dans la mesure où le droit fédéral laisse une marge de manoeuvre au législateur cantonal, le pouvoir d'examen du Tribunal fédéral se limite à l'interdiction de l'arbitraire (<ref-ruling> consid. 2 p. 209 ss.). Dans ces cas, l'<ref-law> exige que l'acte de recours contienne, à peine d'irrecevabilité, un exposé succinct des droits constitutionnels ou des principes juridiques violés et précise en quoi consiste la violation. Lorsqu'il est saisi d'un recours, le Tribunal fédéral n'a donc pas à vérifier de lui-même si l'arrêt entrepris est en tous points conforme au droit et à l'équité. Il n'examine que les griefs d'ordre constitutionnel invoqués et suffisamment motivés dans l'acte de recours (<ref-ruling> consid. 1.3 p. 67; <ref-ruling> consid. 2.1 p. 143).
2. Se fondant sur l'art. 164a al. 5 de la loi fiscale du canton du Valais (LF; RS/VS 642.1), la Commission cantonale de recours en matière fiscale a confirmé le prélèvement d'un intérêt compensatoire négatif à compter de l'échéance cantonale valant pour les impôts cantonaux 2008, à savoir dès le 31 mars 2009. Elle a également approuvé le calcul effectué pour déterminer la somme sur la base de laquelle le montant des intérêts a été calculé, en déduisant du montant de l'impôt dû selon la taxation, 80% du montant de l'impôt anticipé 2005. Ce faisant, l'instance précédente a confirmé l'application par analogie de l'arrêté cantonal du 26 août 1992 relatif à la perception des impôts cantonaux et communaux par acomptes, et en particulier de son article 9.
3. Les recourants ne contestent (<ref-law>) ni la date du terme général d'échéance des impôts cantonaux, fixée au 31 mars 2009, ni la différence entre les impôts facturés et les montants versés à la date du décompte final. Ils ne contestent pas non plus le principe du prélèvement des intérêts compensatoires négatifs, ni leur taux. Ils n'invoquent enfin pas l'application arbitraire de l'arrêté relatif à la perception des impôts cantonaux et communaux par acomptes (RS/VS 642.106; ci-après APICC).
Ils estiment en revanche que l'impôt cantonal 2008 finalement dû est entièrement couvert par le montant de l'impôt anticipé 2008, ce dernier exerçant sur le précédent une fonction de garantie, de sorte qu'aucun intérêt compensatoire ne peut être prélevé. Comme le décompte final présente un solde positif, aucun montant n'était encore dû. L'application de l'art. 164a al. 5 LF et de l'arrêté sur les acomptes provisionnels par analogie violerait le principe de la légalité. Ils soutiennent que la perception d'un « intérêt moratoire » sur l'impôt cantonal sans tenir compte du montant de l'impôt anticipé violerait également les principes de la proportionnalité et de l'interdiction de l'arbitraire. Le principe du respect de la capacité contributive serait également violé par l'exigence du versement d'acomptes provisionnels couvrant l'entier de l'impôt cantonal sans tenir compte des montants de l'impôt anticipé. Les recourants se plaignent enfin de formalisme excessif.
4. Le principe de la légalité régit l'ensemble de l'activité de l'État (cf. art. 5 al. 1 et 36 al. 1 Cst.; voir aussi art. 164 Cst.). Il revêt une importance particulière en droit fiscal où il est érigé en droit constitutionnel indépendant à l'art. 127 al. 1 Cst. Cette norme - qui s'applique à toutes les contributions publiques - prévoit en effet que les principes généraux régissant le régime fiscal, notamment la qualité de contribuable, l'objet de l'impôt et son mode de calcul, doivent être définis par la loi (arrêts 2C_615/2010 du 24 novembre 2010 consid. 3.2; 2C_625/2008 du 30 janvier 2009 consid. 6.2).
La loi s'interprète en premier lieu selon sa lettre (cf. arrêt 6B_593/2011 du 13 avril 2012 consid. 2.1.1). Le sens de la loi est clair lorsqu'il n'y a aucune ambiguïté dans les concepts juridiques employés avec la conséquence que l'on ne saurait s'en écarter (<ref-ruling> consid. 2d). La Cour de céans ne peut exceptionnellement s'écarter de celle-ci que si son interprétation littérale conduirait à des résultats manifestement insoutenables, qui contrediraient la véritable intention du législateur (<ref-ruling> consid. 5.1; <ref-ruling> consid. 2.2; <ref-ruling> consid. 7.1; <ref-ruling> consid. 4.1).
S'il est vrai que le principe de la légalité interdit d'appliquer par analogie des normes fiscales à un état de fait voisin pour combler une lacune et parvenir à une imposition (DANIELLE YERSIN, in Commentaire romand, Impôt fédéral direct, 2008, Remarques préliminaires n° 45), il n'empêche pas qu'en présence non d'une lacune, mais d'un texte peu clair ou ambigu, celui-ci puisse être interprété conformément aux règles générales d'interprétation des textes de loi, notamment en se fondant sur des analogies (cf. par exemple arrêt 2C_598/2007 du 2 juillet 2008 consid. 2-5) et sur les interprétations historique ainsi que téléologique (cf. arrêt 2C_625/2008 du 30 janvier 2009 consid. 6.2). Les travaux préparatoires ne seront pris en considération que s'ils donnent une réponse claire à une disposition légale ambiguë et s'ils ont trouvé expression dans le texte même de la loi (<ref-ruling> consid. 5a; III 324 consid. 7a; <ref-ruling> consid. 2b p. 527; <ref-ruling> consid. 3b/bb p. 196).
5. Une décision est arbitraire lorsqu'elle contredit clairement la situation de fait, lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou lorsqu'elle heurte d'une manière choquante le sentiment de la justice et de l'équité. A cet égard, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si elle apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs ou en violation d'un droit certain. De plus, il ne suffit pas que les motifs de l'arrêt attaqué soient insoutenables, encore faut-il que ce dernier soit arbitraire dans son résultat. (<ref-ruling> consid. 2.4 p. 5; <ref-ruling> consid. 4 p. 560; <ref-ruling> consid. 1 p. 265). En ce sens, l'arbitraire équivaut à une illégalité qualifiée, réalisée lorsque l'autorité a mal interprété et appliqué la loi (Auer/Malinverni/Hottelier, Droit constitutionnel suisse, vol. II, 2e éd, 2006, p. 535 n° 1141).
6. La loi fédérale du 14 décembre 1990 sur l'harmonisation des impôts directs des cantons et des communes (LHID; RS 642.14) ne règle pas, sous réserve de quelques dispositions (not. <ref-law>), la perception des impôts cantonaux et communaux (RDAF 2009 II 99 = StE 2010 B 99.2 no 22, 2C_546/2008 consid. 4.2; Zweifel/Casanova, Schweizerisches Steuerverfahrensrecht, 2008, § 29 n° 2). Seules les dispositions cantonales entrent en ligne de compte. En l'espèce, les dispositions à considérer sont les art. 161 ss LF.
Le droit cantonal prévoit, le cas échéant, deux types d'intérêts à charge du contribuable dans le cadre de l'imposition directe: les intérêts moratoires (art. 164a al. 3 LF) et les intérêts compensatoires négatifs (art. 164a al. 5 LF). Les intérêts moratoires sont dus sur les acomptes impayés ou payés tardivement. Les intérêts compensatoires négatifs sont calculés sur les « montants encore dus » à partir du terme général d'échéance de l'impôt.
Le principe du prélèvement d'intérêts compensatoires négatifs sur la différence entre les impôts facturés et les acomptes a été introduit par décret du Grand Conseil de l'Etat du Valais du 17 juin 2005, entré en vigueur le 1er janvier 2006. Contrairement à ce que soutiennent les recourants, les intérêts compensatoires négatifs n'ont pas le caractère d'une sanction (cf. arrêt 2C_546/2008 consid. 4.2), mais visent à rétablir un déséquilibre financier découlant de l'introduction du système postnumerando. En effet, dans ce système, les contribuables sont taxés au plus tôt au cours de l'année suivante, avec pour conséquence que les collectivités publiques perdent les intérêts pour la part supérieure aux acomptes et doivent de plus rembourser le trop perçu d'impôts au taux des intérêts moratoires. Les intérêts compensatoires sont destinés à réduire les pertes induites par le système (cf. le Message accompagnant le projet de décret concernant la modification de la loi fiscale et du règlement des taxes cadastrales du 22 décembre 2004, par. 2.4.2.2.1).
Compte tenu de ce qui précède, l'interprétation par l'instance précédente des « montants encore dus », sur lesquels doivent porter les intérêts compensatoires négatifs, comme étant ceux résultant de l'imposition directe, n'est pas arbitraire.
7. Selon la doctrine (Ryser/Rolli, Précis de droit fiscal suisse, 1994, p. 13/14; Jean-Marc Rivier, Droit fiscal suisse - L'imposition du revenu et de la fortune, 1980, p. 348; Blumenstein/Locher, System des Steuerrechts, 5e éd., 2002, p. 307), une créance d'impôt se fonde dans tous les cas sur la loi. Elle naît lorsque l'état de fait auquel la loi fiscale rattache l'apparition de la créance d'impôt est réalisé. Ainsi pour qu'un assujettissement fiscal conduise dans un cas d'espèce à la naissance de la créance d'impôt, il faut que les faits générateurs auxquels la loi rattache la perception d'un impôt déterminé soient réunis (<ref-ruling> consid. 4 a), indépendamment de la taxation et de l'exigibilité de l'impôt. La taxation n'a aucun effet constitutif, elle n'est pas une condition de l'existence de la créance d'impôt (<ref-ruling>/29; arrêts des 18 juin 1954, publié in Archives 23, p. 105, 10 janvier 1946, publié in Archives 14 p. 359, et 29 octobre 1943, publié in Archives 12 p. 396; Blumenstein/Locher, op. cit., 2e éd. 2002 p. 394; Rivier, op. cit. p. 348).
Contrairement à la créance de droit civil, en principe immédiatement exigible depuis sa naissance, la créance d'impôt échoit postérieurement à sa naissance (Béguin/Stoyanov, La créance d'impôt, in OREF (éd.), Les procédures en droit fiscal, 2e éd., 2005 p. 808). L'impôt doit être payé et son paiement peut être exigé au terme de son échéance (Rivier, op. cit., p. 217; Béguin/Stoyanov, op. cit., p. 808) dont la date, en matière d'impôts directs est fixée par la loi ou déléguée à l'exécutif, afin que tous les contribuables s'acquittent en même temps de leur dû (Rivier, op. cit., p. 218). Ainsi, la loi fiscale du canton du Valais prévoit que le terme général d'échéance de l'impôt direct est fixé chaque année par le Conseil d'État, par voie de publication officielle (art. 161 al. 1 et 163 al. 2 LF). Le terme général d'échéance de l'impôt était fixé au 31 mars 2009, ce qui n'est pas contesté, de sorte que la créance d'impôt cantonal était exigible dès cette date.
8. La Confédération perçoit un impôt anticipé sur les revenus de capitaux mobiliers, les gains faits dans les loteries et les prestations d'assurances (art. 1 al. 1 de la loi fédérale du du 13 octobre 1965 sur l'impôt anticipé (RS 642.21; LIA). Comme l'impôt anticipé est remboursé aux contribuables domiciliés en Suisse déclarant correctement les rendements qui en sont frappés, l'impôt anticipé a une fonction de garantie des impôts sur le revenu et la fortune, ne visant toutefois que les revenus imposables tels que définis par la LIA (MAJA BAUER-BALMELLI/MARKUS NYFFENEGGER, in Kommentar zum Schweizerischen Steuerrecht II/2, 2005, n° 67 et 68 ad Vorbemerkungen; voir également MAJA BAUER-BALMELLI, Die Sicherungszweck der Verrechnungssteuer, 2000, p. 212 ss). En ce sens, il a un but fiscal indirect, dans la mesure où il est restitué lorsque la possibilité de percevoir les impôts sur le revenu et la fortune est assurée, et un but fiscal direct subsidiaire, lorsqu'il est définitivement retenu en raison de l'absence de réalisation des conditions de sa restitution (arrêt 2C_333/2007 du 22 février 2008 consid. 7.3; BAUER-BALMELLI, op. cit., 2000, p. 216-217). Le but fiscal indirect est en un certain sens abstrait, car il ne vise que la garantie de la possibilité de taxer le contribuable selon les dispositions ordinaires régissant les impôts sur les revenus et la fortune ou autrement dit, à décourager le contribuable de soustraire à l'impôt ordinaire les montants frappés par l'impôt anticipé (arrêt 2C_333/2007 du 22 février 2008 consid. 7.3; BAUER-BALMELLI, op. cit., 2000, p. 216). La fonction de cette garantie est remplie aussitôt que la déclaration des montants soumis à l'impôt est effectuée en bonne et due forme, dans le délai imparti (BAUER-BALMELLI, op. cit., 2000, p. 215 et 216-217). De la sorte, l'impôt anticipé n'a pas pour fonction de garantir une somme mais d'encourager le contribuable à remplir ses obligations fiscales en vertu du droit cantonal et intercantonal. En d'autres termes, l'impôt anticipé ne saurait soustraire le contribuable à ses obligations en matière d'imposition directe.
9. La prétention en remboursement de l'impôt anticipé, formulée par écrit par le contribuable au plus tard au moment de la déclaration d'impôt, doit faire l'objet d'une décision de l'autorité fiscale, tant sur son principe que sur sa quotité (<ref-law>; art. 5 al. 1 et 34 ss de la loi fédérale du 20 décembre 1968 sur la procédure administrative [PA; RS 172.021]; Pfund/Zwahlen, Verrechnungssteuer, 2e partie, 1985, n° 2.3 ad art. 29). Elle est imputée sur les impôts cantonaux et communaux qui doivent être payés pour la même année (art. 31 al. 1 et 3 LIA). Si après imputation, le décompte final présente un solde en faveur des contribuables, celui-ci est versé en espèces (<ref-law>). Les montants à imputer ou à rembourser ne portent pas intérêt (<ref-law>). La procédure de remboursement aboutissant à une décision repose sur le droit cantonal (<ref-law>).
L'ordonnance cantonale d'application de la loi fédérale sur l'impôt anticipé et de l'ordonnance fédérale relative à l'imputation forfaitaire d'impôt (RS/VS 642/200; ci-après OALIA) prévoit que le remboursement aux personnes physiques est effectué sous la forme d'imputation sur l'impôt cantonal dû sur le revenu et la fortune ou sur la dépense (art. 5 al. 1 OALIA). La mise en compte définitive de l'impôt anticipé s'opère dans le décompte final des impôts cantonaux sur le revenu et la fortune, notifiés au contribuable (art. 5 al. 2 OALIA). Enfin, l'échéance générale de l'impôt anticipé est fixée au 10 décembre de l'année suivante, conformément à l'art. 5 al. 2 de l'arrêté cantonal relatif à la perception des impôts cantonaux et communaux par acomptes du 26 août 1992 (RS/VS 642.106; ci-après APICC).
10. Les recourants considèrent que l'application par analogie de l'art. 9 APICC, afin de déterminer le montant sur lequel est calculé l'intérêt moratoire négatif, viole le principe de la légalité. Cet article prévoit qu'il est imputé un impôt anticipé présumé sur les acomptes d'impôts cantonaux des personnes physiques. L'imputation est effectuée sur la première tranche d'impôt et l'excédent éventuel sur les tranches suivantes (al. 1). L'impôt anticipé supputé est fixé à 80 pour cent du dernier impôt anticipé bonifié, à l'exclusion de l'impôt grevant les revenus casuels (al. 2). La Commission cantonale considère pour sa part que l'application de l'arrêté cantonal "relève de la logique" et soutient qu'il s'agit "d'une solution favorable [aux recourants] dont ils ne sauraient se plaindre".
Le raisonnement par analogie, qui permet d'étendre le champ d'application d'une norme aux situations comparables à celles qu'elle régit expressément, n'est possible qu'après détermination de la portée véritable de la norme selon les méthodes d'interprétation ordinaires (arrêt 1P.97/1997 du 20 août 1997 consid. 2c). Il ressort des travaux préparatoires que la prise en compte de l'impôt anticipé vise à éviter d'exiger l'entier du paiement des impôts directs, alors que l'Etat sait qu'il devra rembourser l'impôt anticipé - dont le terme général d'échéance est postérieur - ce qui se justifie tant pour la facturation par le biais des acomptes provisionnels que pour le paiement à l'échéance générale, de sorte que l'application par analogie de l'APICC ne paraît pas arbitraire.
11. Il résulte des considérations qui précèdent que, comme il n'est pas contesté que les recourants n'ont pas payé l'entier des impôts cantonaux à la date d'échéance générale de l'impôt, les conditions de l'art. 164a al. 5 LF étaient réalisées. C'est sur ce solde impayé, auquel est appliqué l'art. 9 APICC par analogie, que porte l'intérêt compensatoire négatif, jusqu'à l'extinction de la créance. Contrairement à ce que plaident les recourants, l'impôt anticipé 2008 ne pouvait être imputé rétroactivement dès l'échéance générale de l'impôt cantonal, soit avant même d'être exigible. L'extinction de la créance par imputation de l'impôt anticipé 2008 au 10 décembre 2009 seulement n'est ainsi pas arbitraire.
12. Les recourants soutiennent que l'exigence du versement de l'entier de l'impôt cantonal est disproportionnée et viole l'art. 5 al. 2 Cst., ainsi que le principe de l'imposition selon la capacité économique.
Comme il résulte des développements qui précèdent que les dispositions cantonales, qui prennent en compte la créance en remboursement de l'impôt anticipé, ont été appliquées correctement, il n'y pas lieu d'examiner si les garanties susmentionnées ont été violées.
13. Se plaignant de s'être vus refuser une solution transactionnelle à leur avantage, les recourants invoquent l'interdiction du formalisme excessif (art. 29 al. 1 Cst.).
Ce principe protège contre l'application d'une règle de procédure qui n'est justifiée par aucun intérêt digne de protection, de sorte qu'elle devient une fin en soi, complique de manière insoutenable la mise en ?uvre du droit matériel ou entrave de manière inadmissible l'accès aux tribunaux (cf. <ref-ruling> consid. 2a).
On ne voit pas en l'espèce de quelle norme les recourants tirent un droit à une solution transactionnelle, de sorte qu'insuffisamment motivé, ce grief doit être rejeté (art. 106 al. 2 Cst.).
14. Compte tenu de ce qui précède, le recours en matière de droit public doit être rejeté.
Succombant, les recourants supporteront les frais judiciaires (<ref-law>) solidairement entre eux. Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants.
3. Le présent arrêt est communiqué aux mandataires des recourants, au Service cantonal des contributions et à la Commission cantonale de recours en matière fiscale du canton du Valais ainsi qu'à l'Administration fédérale des contributions.
Lausanne, le 7 août 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Cavaleri Rudaz