Faits :
A.
X._, né en 1992 et domicilié en Valais, a été victime d'un accident de la route, le 3 août 2011, qui lui a causé une paraplégie complète.
Le 7 novembre 2012, l'intéressé a adressé un certificat médical à l'Office cantonal des affaires militaires du canton du Valais (ci-après: l'Office cantonal). Le 17 décembre 2012, il a été déclaré inapte au service.
B.
La Section cantonale de la taxe d'exemption de l'obligation de servir du canton du Valais (ci-après: la Section cantonale) a taxé l'intéressé pour les années 2011 à 2014. Les décisions de taxation pour les années 2012 et 2013 ont été notifiées les 27 novembre 2013, respectivement 17 septembre 2014. X._ s'est acquitté de la totalité de la taxe d'exemption de l'obligation de servir de l'année 2012 et d'une partie de celle de l'année 2013.
C.
Le 15 décembre 2014, X._ a notamment demandé à la Section cantonale de reconsidérer les taxes d'exemption pour les années 2012 à 2014, de rectifier les taxations pour ces années et de rembourser les versements effectués à tort. Par deux décisions du 6 janvier 2015, la Section cantonale, après avoir considéré l'écriture de l'intéressé comme une réclamation, a déclaré irrecevables les réclamations pour les années 2012 et 2013. Dans une décision subséquente du 30 mars 2015 (<ref-law>), elle a exonéré X._ de la taxe d'exemption de l'obligation de servir pour l'année 2014. L'intéressé a contesté les décisions sur réclamation relatives aux années 2012 et 2013 auprès de la Commission cantonale de recours en matière fiscale du canton du Valais (ci-après: la Commission de recours) le 19 janvier 2015.
Par arrêt du 14 octobre 2015, la Commission de recours a admis le recours de X._. Elle a jugé en bref que l'Office cantonal n'avait pas transmis le certificat médical au Service cantonal, ce qui avait empêché ce dernier d'exonérer l'intéressé de la taxe d'exemption de l'obligation de servir. Les décisions de taxation ont ainsi été rendues sans qu'il ne soit tenu compte d'un fait important, établi par pièce. Reprocher à l'intéressé de ne pas avoir vérifié que les autorités aient correctement pris en compte les informations transmises aurait été contraire à la bonne foi et au principe de l'interdiction de formalisme excessif.
D.
Agissant par la voie du recours en matière de droit public, l'Administration fédérale des contributions demande au Tribunal fédéral, sous suite de frais, d'annuler la décision du 14 octobre 2015 de la Commission de recours, de confirmer les décisions de taxation des 27 novembre 2013 et 17 septembre 2014 et de confirmer les décisions sur réclamation du 6 janvier 2015. Elle se plaint de violation du droit fédéral.
La Section cantonale conclut implicitement à l'admission du recours. La Commission de recours et X._ concluent tous deux au rejet du recours.

Considérant en droit :
1.
Le recours est dirigé contre une décision rendue dans une cause de droit public (<ref-law>) ne tombant pas sous le coup de l'une des exceptions prévues à l'<ref-law> (cf. art. 31 al. 3 de la loi du 12 juin 1959 sur la taxe d'exemption de l'obligation de servir [LTEO; RS 661]). Il a été déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par l'Administration fédérale qui a qualité pour recourir en matière de taxe d'exemption de l'obligation de servir (cf. <ref-law> et 4 al. 1 de l'ordonnance fédérale du 17 février 2010 sur l'organisation du Département fédéral des finances [Org DFF; RS 172.215.1]). Le jugement contesté est une décision finale (<ref-law>) et a en outre été rendu par une autorité judiciaire de dernière instance cantonale (art. 86 al. 1 let. d et al. 2 LTF). Le recours est par conséquent recevable.
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), alors qu'il n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant, conformément au principe d'allégation (<ref-law>). Dans ce cas, l'acte de recours doit, sous peine d'irrecevabilité, contenir un exposé succinct des droits et principes constitutionnels violés et préciser en quoi consiste la violation (<ref-ruling> consid. 2.5 p. 314; <ref-ruling> consid. 2 p. 248). Par ailleurs, le Tribunal fédéral conduit son raisonnement en se fondant sur les faits constatés par l'autorité précédente (cf. <ref-law>), sous réserve des cas prévus à l'<ref-law>. Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire (<ref-ruling> consid. 2.4 p. 313 s.), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid. 4.2 p. 233 s.). Conformément à l'<ref-law>, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits et les critiques invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 5.1 p. 356). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal de céans (<ref-law>).
3.
Il ressort des faits retenus par l'autorité précédente que les deux décisions contestées par l'intimé sont entrées en force et que ce dernier s'est en partie acquitté du montant des deux taxes (seul un peu plus de 14% de la taxe pour 2013 est resté impayé). L'Office cantonal, auquel l'intimé a adressé son certificat médical attestant de sa paraplégie complète, n'a pas transmis ce document au Service cantonal chargé de taxer l'intimé. Ce n'est que lorsque l'intimé a demandé la reconsidération de ses taxations 2012 et 2013 au Service cantonal, le 15 décembre 2014, que celui-ci a pris connaissance de sa paraplégie. Il a alors exempté l'intimé de la taxe pour l'année 2014, mais n'est pas entré en matière sur une reconsidération des taxes d'exemption de l'obligation de servir pour les années 2012 et 2013. Sur recours, l'autorité précédente a implicitement considéré que le Service cantonal avait faussement exclu un cas de révision et a exonéré l'intimé de la taxe d'exemption de l'obligation de servir pour les années 2012 et 2013.
La recourante estime qu'il ne saurait être question d'un cas de révision en l'espèce et que c'est à tort que la Commission de recours est entrée en matière sur la demande de l'intimé. La recourante exclut en outre l'existence d'une situation exceptionnelle qui permettrait de déroger aux principes régissant la révision, l'intimé n'ayant pas été empêché de faire recours dans le délai légal et ayant été valablement averti de cette possibilité et des cas d'exonération du paiement de la taxe pour les personnes atteintes d'un handicap. L'intimé fait quant à lui en substance valoir que son état de santé à l'époque des notifications des décisions relatives à la taxe d'exemption de l'obligation de servir pour les années 2012 et 2013 ne lui permettait pas de faire recours et qu'il ne se doutait pas qu'il pouvait être exonéré de la taxe.
4.
Le litige porte sur la taxe d'exemption de l'obligation de servir pour les années 2012 et 2013. Cette taxe est régie par le droit fédéral, en particulier par la LTEO et par l'ordonnance du 30 août 1995 sur la taxe d'exemption de l'obligation de servir (OTEO; RS 661.1). Les décisions de taxation ainsi que les décisions sur l'exonération ou la réduction de la taxe peuvent faire l'objet d'une réclamation écrite à l'autorité de taxation, dans les 30 jours suivant leur notification (<ref-law>). D'après l'<ref-law>, ce délai peut être restitué à condition notamment que l'assujetti ait été, sans sa faute, empêché d'agir dans le délai fixé et qu'il présente une demande motivée de restitution dans le délai de dix jours dès la cessation de l'empêchement. L'<ref-law> prévoit quant à lui la possibilité pour l'assujetti d'obtenir la restitution d'un montant de taxe payé par erreur, s'il ne devait pas la taxe ou n'en devait qu'une partie. Cette disposition correspond à l'<ref-law> (RS 642.11; FF 2002 816 p. 846) et a la même portée. Il ressort du texte de ces dispositions que seule la perception de la taxe est visée et non la procédure de taxation. La demande de restitution de taxes payées par erreur ne permet donc pas de remettre en cause une décision de taxation passée en force. Seule la voie de la procédure de révision permet de modifier une telle décision (cf., par analogie, PIERRE CURCHOD, Commentaire romand, Impôt fédéral direct, n° 1, 6 et 7 ad <ref-law>).
En l'occurrence, il ne ressort pas des faits retenus par l'autorité précédente que l'intimé aurait fait valoir un empêchement au sens de l'<ref-law>. Il l'invoque certes implicitement devant le Tribunal fédéral, toutefois tardivement et sans expliquer plus avant en quoi il aurait été empêché. L'<ref-law> ne lui est en outre d'aucun secours, dès lors que les montants qu'il a (partiellement) payés correspondent à ceux figurant dans les décisions de taxation entrées en force. C'est ainsi à juste titre que la Commission de recours a traité le courrier du contribuable comme un recours contre une décision d'irrecevabilité relative à une demande de révision. Il convient donc de se demander si la requête de l'intimé remplissait les conditions ouvrant la voie de la révision.
5.
5.1. L'<ref-law> confie, entre autres, au Conseil fédéral la compétence de fixer des règles qui concernent la révision des décisions passées en force. Quant à l'<ref-law>, il dispose que l'autorité de taxation ou la commission de recours procède à la révision d'une décision entrée en force, d'office ou à la demande de la personne touchée par celle-ci si des faits nouveaux importants sont allégués ou de nouveaux moyens de preuve produits (let. a); si l'autorité n'a pas tenu compte de faits ou de demandes importants établis par pièces (let. b); si l'autorité a violé des principes essentiels de la procédure, en particulier le droit de consulter les pièces et celui d'être entendu (let. c). L'<ref-law> dispose quant à lui que la révision est exclue lorsque le requérant invoque des motifs qu'il aurait pu faire valoir au cours de la procédure ordinaire s'il avait fait preuve de toute la diligence pouvant raisonnablement être exigée de lui.
5.2. Ces motifs de révision correspondent à ceux prévus à l'art. 147 al. 1 et 2 LIFD, de sorte que l'on peut, dans leur interprétation, se fonder sur la jurisprudence et la doctrine relatives à l'impôt fédéral direct (arrêt 2C_564/2008 du 12 septembre 2008 consid. 5). Pour être qualifié d'important, un fait doit être de nature à influencer la décision dans un sens favorable à l'intéressé (cf. <ref-ruling> consid. 3 p. 18 s. et la jurisprudence citée; arrêt 2C_941/2015 du 9 août 2016 consid. 6.3). Quant à l'exclusion de la révision dès que l'on peut reprocher au requérant d'avoir failli à la diligence, qui est prévue tant à l'<ref-law> qu'à <ref-law>, elle constitue une limitation importante à la révision, qui s'explique par le caractère subsidiaire de cette voie de droit et par les exigences de la sécurité du droit (HUGO CASANOVA, Commentaire romand, Impôt fédéral direct, n° 15 ad <ref-law>). La jurisprudence souligne du reste qu'il faut se montrer strict dans l'obligation de diligence imposée au requérant (cf. arrêt 2F_12/2014 du 12 février 2015 consid. 3.1). Une révision est ainsi exclue en cas d'erreur dans la déclaration d'impôt due à une négligence du contribuable ou de son représentant (arrêt 2C_564/2008 précité consid. 5; HUGO CASANOVA, op. cit., n° 15 ad <ref-law>). Il appartient en outre au contribuable de contrôler la décision de taxation lorsqu'il la reçoit et de signaler en temps utile les vices dont elle serait affectée (cf. arrêts 2C_941/2015 précité consid. 6.3; 2C_564/2008 précité consid. 5 et les références citées).
5.3. S'il est effectivement regrettable qu'au sein d'une même administration cantonale les informations pertinentes à la prise d'une décision ne soient pas transmises, force est toutefois de constater qu'il ne saurait être question, en l'espèce, d'un cas de révision. En effet, sans qu'il soit nécessaire de déterminer dans quelle mesure les conditions de l'<ref-law> seraient réunies, l'examen de l'<ref-law> suffit pour exclure un cas de révision. Alors qu'il a reçu une décision de taxation le 27 novembre 2013, puis une autre le 17 septembre 2014, l'intimé s'est à chaque fois vu remettre une notice explicative mentionnant les cas dans lesquels une exonération de la taxe d'exemption de l'obligation de servir est admise (<ref-law>). Il ne pouvait donc ignorer qu'un handicap semblable au sien pouvait conduire à une exonération. A ce propos, on peut s'étonner que les deux décisions des années 2012 et 2013, éléments pertinents quant à l'examen de la présente cause, aient été produites par la recourante et qu'elles ne figurent pas au dossier de l'autorité précédente, qui se doit pourtant de transmettre un dossier complet au Tribunal fédéral (cf. <ref-law>). Quand bien même ces éléments n'auraient, de manière surprenante, pas été à la disposition de la Commission de recours, celle-ci ne pouvait pas admettre que l'intimé, en faisant preuve de toute la diligence nécessaire, ignorait que son handicap constituait une cause d'exonération et qu'il lui appartenait de recourir contre la décision de taxation pour invoquer ce grief. Dans ces conditions, en application de l'<ref-law>, c'est à tort que l'autorité précédente a admis un cas de révision. On ajoutera finalement que, contrairement à ce que relève la Commission de recours, il n'est pas possible, sous l'empire de la LIFD, de déroger aux principes régissant la révision, si le résultat de leur application est choquant et heurte le sentiment de l'équité. Un tel raisonnement revient en effet à déroger à la règle du numerus clausus des motifs légaux qui permettent de revenir sur une décision entrée en force (arrêts 2C_322/2015 du 4 avril 2016 consid. 3.4; 2C_961/2014 du 8 juillet 2015 consid. 3.2, in Archives 84 p. 251; 2C_200/2014 du 4 juin 2015 consid. 2.4.1, in RF 70/2015 p. 711 et Archives 84 p. 250)
6.
Les considérants qui précèdent conduisent à l'admission du recours, à l'annulation de la décision du 14 octobre 2015 de la Commission de recours et à la confirmation des décisions sur réclamation de la Section cantonale du 6 janvier 2015.
Compte tenu des circonstances du cas d'espèce, il y a exceptionnellement lieu de renoncer à la perception de frais pour la procédure fédérale (<ref-law>). Il n'y a pas lieu d'allouer des dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis. La décision du 14 octobre 2015 de la Commission cantonale de recours en matière fiscale est annulée et les décisions du 6 janvier 2015 de la Section cantonale de la taxe d'exemption de l'obligation de servir confirmées.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le présent arrêt est communiqué à la recourante et à l'intimé, ainsi qu'à la Section cantonale de la taxe d'exemption de l'obligation de servir et à la Commission de recours en matière fiscale du canton du Valais.
Lausanne, le 6 septembre 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette