Sachverhalt:
A. X._ (geb. 1947) und Z._ (geb. 1946) heirateten im August 1976. Sie wurden Eltern von vier Kindern.
Gestützt auf ein gemeinsames Begehren der Ehegatten vom 3. März 2006 und der damit eingereichten Vereinbarung über sämtliche Scheidungsfolgen sprach das Landgerichtspräsidium Uri mit Urteil vom 12. Juli 2006 die Scheidung aus, genehmigte die von den Parteien unterzeichnete Vereinbarung über die Scheidungsfolgen und erklärte diese zum Bestandteil des Urteilsdispositivs (Ziff. 2 des Dispositivs). In der Ziff. 3 der Vereinbarung über die Scheidungsfolgen regelten die Parteien den nachehelichen Unterhalt wie folgt:
3. Nachehelicher Unterhalt
a) Der Ehemann wird verpflichtet, seiner Ehefrau ab Rechtskraft des Scheidungsurteils bis zum Zeitpunkt, in welchem Sohn (...) seine Erstausbildung abgeschlossen hat, längstens aber bis zum Zeitpunkt seiner Pensionierung, einen Unterhaltsbeitrag von Fr. 1'050.-- zu bezahlen. (...).
b) Der Ehemann verpflichtet sich, der Ehefrau - sofern Sohn (...) seine Erstausbildung abgeschlossen hat - einen Unterhaltsbeitrag von Fr. 1'500.-- bis längstens zum Zeitpunkt seiner Pensionierung zu bezahlen. (...).
c) Der Ehemann wird verpflichtet, der Ehefrau ab dem Zeitpunkt seiner Pensionierung einen Unterhaltsbeitrag zu bezahlen, sofern eine dannzumal vorzunehmende Berechnung der Existenzminima und Unterhaltsbeiträge eine entsprechende Zahlungspflicht ergibt. Der Ehemann wird in diesem Zusammenhang verpflichtet, vor dem Zeitpunkt seiner Pensionierung die entsprechenden Berechnungen vorzunehmen, damit diese - sofern eine Änderung des Scheidungsurteils notwendig ist - direkt dem Landgerichtspräsidium Uri mit einem Änderungsantrag eingereicht werden können.
d) [Indexierung].
Per 31. Mai 2009 trat X._ in den vorzeitigen Ruhestand.
B. Mit Klage vom 22. Juli 2009 gegen Z._ verlangte X._, in Abänderung des Scheidungsurteils sei festzustellen, dass er ihr seit dem 1. Juni 2009 keinen nachehelichen Unterhalt mehr auszurichten habe. Eventualiter sei in Abänderung des Scheidungsurteils festzustellen, dass er ihr keinen nachehelichen Unterhalt auszurichten habe.
Das Landgericht Uri wies die Klage mit Entscheid vom 21. Januar 2010 ab.
C. Dagegen gelangte X._ am 12. Mai 2010 mit Berufung an das Obergericht des Kantons Uri. Er verlangte, der landgerichtliche Entscheid sei aufzuheben und formulierte in der Sache leicht abgeänderte Anträge.
Mit Entscheid vom 16. Juni 2011 wies das Obergericht die Berufung ab, soweit es darauf eintrat und bestätigte soweit vorliegend massgebend den Entscheid des Landgerichts.
D. Dem Bundesgericht beantragt X._ (nachfolgend Beschwerdeführer) in seiner Beschwerde in Zivilsachen und subsidiären Verfassungsbeschwerde vom 24. Oktober 2011, der obergerichtliche Entscheid sei aufzuheben und seine "Anträge gemäss der Berufung vom 12. Mai 2010 seien gutzuheissen". Eventualiter sei die Sache zu neuer Beurteilung an das Obergericht zurückzuweisen.
Das Obergericht hat dem Bundesgericht die Vorakten zugestellt, auf eine Vernehmlassung hingegen verzichtet (Schreiben vom 9. Januar 2012). Z._ (nachfolgend Beschwerdegegnerin) beantragt in ihrer Vernehmlassung vom 30. Januar 2012, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.

Erwägungen:
1. Der angefochtene Endentscheid betrifft die Abänderung eines Scheidungsurteils in Bezug auf den nachehelichen Unterhalt und damit eine Zivilsache vermögensrechtlicher Natur, wobei der erforderliche Streitwert überschritten ist (Art. 90, Art. 72 Abs. 1 und Art. 74 Abs. 1 lit. b BGG). Die rechtzeitig (Art. 100 Abs. 1 i.V.m. <ref-law>) erhobene Beschwerde richtet sich gegen den Entscheid eines oberen Gerichts, das kantonal letztinstanzlich auf Rechtsmittel hin geurteilt hat (<ref-law>). Die Beschwerde in Zivilsachen ist damit zulässig. Die in der gleichen Rechtsschrift erhobene subsidiäre Verfassungsbeschwerde wird hinfällig (<ref-law>; <ref-ruling> E. 1.2 S. 400).
2. Das Landgericht hat seinen Entscheid am 21. Januar 2010 im Dispositiv und am 22. April 2010 in vollständiger Ausfertigung den Parteien versandt. Gemäss den Übergangsbestimmungen der am 1. Januar 2011 in Kraft getretenen Schweizerischen Zivilprozessordnung (ZPO; SR 272) war damit für das landgerichtliche Verfahren und für das kantonale Rechtsmittel das bisherige Verfahrensrecht, das heisst die Zivilprozessordnung des Kantons Uri vom 23. März 1994 (ZPO/UR; in Kraft bis 31. Dezember 2010), anwendbar (Art. 404 f. ZPO; vgl. <ref-ruling> E. 2 S. 129 f.; <ref-ruling> E. 2 S. 131 f.).
3.1 3.1.1 Neue Begehren sind vor Bundesgericht unzulässig (<ref-law>). Als neu haben auch solche Begehren zu gelten, die in der letzten kantonalen Instanz nicht in prozessual wirksamer Weise geltend gemacht wurden (<ref-ruling> E. 8.3 S. 530; <ref-ruling> E. 2b S. 154; MEYER, Wege zum Bundesgericht - Übersicht und Stolpersteine, ZBJV 146/2010 S. 878).
3.1.2 Das Obergericht hat die Berufung des Beschwerdeführers abgewiesen, soweit es darauf eintrat. Wie aus der Urteilsbegründung hervorgeht, die zur Ermittlung der Tragweite des Dispositivs beizuziehen ist (<ref-ruling> E. 2.1 S. 348; <ref-ruling> E. 4a S. 478), ist das Obergericht auf die Berufung insoweit nicht eingetreten, als der Beschwerdeführer seine Klagebegehren im Vergleich zu seinen Begehren vor dem Landgericht abgeändert hatte. Das Obergericht hat die Voraussetzungen für eine Klageänderung gemäss <ref-law>/UR nicht als gegeben erachtet. Hingegen prüfte es die Klage anhand der ursprünglich vor dem Landgericht gestellten Begehren.
3.1.3 Vor Bundesgericht beantragt der Beschwerdeführer, der obergerichtliche Entscheid sei aufzuheben und seine "Anträge gemäss der Berufung vom 12. Mai 2010 seien gutzuheissen".
Soweit der Beschwerdeführer damit vor Bundesgericht seine vom Obergericht als unzulässig erklärten Rechtsbegehren wiederholt, erweisen sich diese als neu und unzulässig. Insoweit ist auf die Beschwerde nicht einzutreten (<ref-law>). Er beanstandet denn vor Bundesgericht auch nicht, dass das Obergericht von einer Klageänderung ausgegangen und insoweit nicht auf die Berufung eingetreten ist.
Rechtsbegehren sind im Lichte der Beschwerdebegründung auszulegen (<ref-ruling> E. 6.2 S. 622; <ref-ruling> E. 1.4.1 S. 415). Aus der Beschwerdebegründung ergibt sich zweifelsfrei, dass der Beschwerdeführer neben seinen neuen und damit wie soeben erwähnt unzulässigen Begehren auch an seinen (vom Obergericht schliesslich geprüften) Rechtsbegehren, wie er sie vor dem Landgericht gestellt hatte, festhält. Insoweit erweisen sich seine Anträge als zulässig.
3.2 Der Beschwerdeführer wendet sich vor Bundesgericht auch gegen den Entscheid des Landgerichts und wirft der ersten Instanz eine Verletzung seines Anspruchs auf rechtliches Gehör vor (Ziff. 19 der Beschwerde).
Anfechtungsobjekt vor Bundesgericht ist nicht das Urteil des Landgerichts, sondern dasjenige des Obergerichts (<ref-law>), das auf Berufung hin sämtliche Tat- und Rechtsfragen frei prüfen konnte (vgl. <ref-law>/UR). Die Rügen gegen das landgerichtliche Urteil erweisen sich deshalb als unzulässig (vgl. <ref-ruling> E. 1.3 S. 527).
4. 4.1 Die Beschwerde ist zu begründen (<ref-law>). Es ist in gedrängter Form durch Auseinandersetzung mit den Erwägungen des angefochtenen Entscheids darzulegen, welche Rechtssätze und inwiefern sie durch den angefochtenen Entscheid verletzt worden sind. Die Gesetzesartikel brauchen allerdings nicht ausdrücklich genannt zu werden, falls aus den Vorbringen hervorgeht, gegen welche Regeln die Vorinstanz verstossen haben soll. Allgemein gehaltene Einwände, die ohne aufgezeigten oder erkennbaren Zusammenhang mit bestimmten Entscheidungsgründen vorgebracht werden, genügen nicht, da das Bundesgericht nicht gehalten ist, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen (<ref-ruling> E. 1.3 S. 584; <ref-ruling> E. 3.3 S. 60).
4.2 Die Verletzung von Grundrechten prüft das Bundesgericht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und gehörig begründet wird (<ref-law>). Der Beschwerdeführer muss präzise angeben, welches verfassungsmässige Recht verletzt wurde und substanziiert anhand der Erwägungen des angefochtenen Entscheids darlegen, worin die Verletzung besteht. Das Bundesgericht prüft nur ausdrücklich vorgebrachte, klar und detailliert erhobene sowie, soweit möglich, belegte Rügen (<ref-ruling> E. 3.3 S. 310 f.; <ref-ruling> E. 2.2 S. 246).
5. 5.1 Der Beschwerdeführer rügt eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>), da es dem obergerichtlichen Entscheid teilweise an einer Begründung fehle (vgl. zur Pflicht der Behörde, ihren Entscheid zu begründen: <ref-ruling> E. 4.2 S. 355). Das Obergericht sei auf seine Rügen betreffend der Verletzung von Verfahrensrecht sowie betreffend die landgerichtliche Kostenverlegung nicht oder nur in wenigen Sätzen eingegangen (Ziff. 30 und 35 der Beschwerde).
5.2 Mit diesen kurzen Begründungen vermag der Beschwerdeführer den aufgezeigten Anforderungen für die Begründung von Verfassungsrügen nicht zu genügen. Insbesondere unterlässt er es, mit Aktenhinweisen aufzuzeigen, welche seiner in der Berufungsschrift erhobenen Vorbringen das Obergericht übergangen haben soll. Darauf ist nicht einzutreten (<ref-law>; vgl. E. 4.2 oben).
5.3 Der Beschwerdeführer rügt sodann eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>), soweit das Obergericht (wie bereits das Landgericht) die von ihm eingereichten Beweismittel nicht berücksichtigt habe (Ziff. 33 der Beschwerde).
Der Beschwerdeführer vermag auch insoweit den bundesgerichtlichen Begründungsanforderungen nicht zu genügen. Er unterlässt es - wiederum unter Verweis auf die Akten - darzulegen, dass er die entsprechenden Tatsachenbehauptungen aufgestellt und prozesskonform dazu Beweis angeboten hat (<ref-ruling> E. 7.1 S. 299). Darauf ist nicht einzutreten (<ref-law>; vgl. E. 4.2 oben) und es erübrigen sich von vornherein weitere Ausführungen zu dieser Rüge (vgl. insbesondere zum Verhältnis zwischen <ref-law> und <ref-law>: Urteil 5A_726/2009 vom 30. April 2010 E. 3.1, nicht publ. in: <ref-ruling>).
5.4 Weiter rügt der Beschwerdeführer, das Obergericht verletze "den Gehalt von <ref-law>", da es sich zu seiner in der Berufungseingabe erhobenen Rüge, das Landgericht habe es unterlassen, einen Beweisentscheid zu fällen, ausschweige (Ziff. 34 der Beschwerde).
Auch diese Begründung vermag den Begründungsanforderungen für Verfassungsrügen nicht zu genügen. Der Beschwerdeführer legt nicht rechtsgenüglich dar, welchen Gehalt von <ref-law> er überhaupt als verletzt erachtet. Darauf ist nicht einzutreten (<ref-law>; vgl. E. 4.2 oben).
6.1 6.1.1 Um die Abänderungsklage des Beschwerdeführers zu beurteilen, legte das Obergericht in einem ersten Schritt fest, wie "Pensionierung" gemäss Ziff. 2/3 des Scheidungsurteils zu verstehen ist. Es erwog zusammenfassend (teilweise durch Verweis auf den landgerichtlichen Entscheid), der im Scheidungsurteil verwendete Begriff der "Pensionierung" sei vorliegend nach dem Vertrauensprinzip auszulegen, da der wirkliche Wille der Parteien nicht mehr festgestellt werden könne. Die Anwendung des Vertrauensprinzips stelle eine Rechtsfrage dar. Dabei müsse man sich jedoch auf den Inhalt der Willensäusserung und auf die Umstände, welche zum Sachverhalt gehörten, stützen.
Das Obergericht gelangte zum Ergebnis, mit dem im Scheidungsurteil verwendeten Begriff "Pensionierung" sei das ordentliche AHV-Alter von 65 Jahren (<ref-law>) gemeint gewesen. Die Pflicht des Beschwerdeführers zur Leistung des nachehelichen Unterhalts gemäss Ziff. 2/3a und 2/3b sei damit noch nicht weggefallen.
6.1.2 In einem zweiten Schritt prüfte das Obergericht sodann, ob der per 31. Mai 2009 erfolgte (vorzeitige) Eintritt des Beschwerdeführers in den Ruhestand eine erhebliche, dauernde und unvorhersehbare Veränderung gemäss <ref-law> darstellt. Es hielt dazu fest, bei einem Altersrücktritt fehle es von vornherein an der Unvorhersehbarkeit.
6.2 Der Beschwerdeführer rügt eine "Rechtsverletzung", da die obergerichtliche Auslegung des Begriffs "Pensionierung" nicht haltbar sei (Ziff. 22 und 26 der Beschwerde).
Der Beschwerdeführer begnügt sich wiederholt mit dem Hinweis, dem Obergericht sei eine Rechtsverletzung vorzuwerfen, ohne dass aus der Begründung ersichtlich würde, welchen Rechtssatz er als verletzt erachtet. Darauf ist nicht einzutreten (<ref-law>; vgl. E. 4.1 oben).
Der Beschwerdeführer begnügt sich wiederholt mit dem Hinweis, dem Obergericht sei eine Rechtsverletzung vorzuwerfen, ohne dass aus der Begründung ersichtlich würde, welchen Rechtssatz er als verletzt erachtet. Darauf ist nicht einzutreten (<ref-law>; vgl. E. 4.1 oben).
6.3 6.3.1 Weiter bringt der Beschwerdeführer vor, das Obergericht hätte die Voraussetzung der Unvorhersehbarkeit gar nicht prüfen dürfen, weshalb es <ref-law> verletze. Er habe einzig die Feststellung anbegehrt, wie der Begriff "Pensionierung" zu verstehen sei; eine Abänderung des Scheidungsurteils, welche die Voraussetzungen von <ref-law> erfüllen müsste, habe er gar nicht verlangt.
6.3.2 Es kann offen gelassen werden, ob dem Beschwerdeführer die Erläuterung gemäss <ref-law>/UR (vgl. insoweit das mit dem vorliegenden Sachverhalt vergleichbare Urteil 5A_493/2011 vom 12. Dezember 2011 mit Hinweisen) zur Verfügung gestanden hätte, wenn es ihm tatsächlich wie behauptet einzig um die Frage gegangen wäre, wie das Scheidungsurteil zu verstehen ist. Vielmehr legt er nämlich auch noch vor Bundesgericht an anderer Stelle seiner Beschwerde dar, es handle sich bei seiner Eingabe um eine Abänderungsklage nach <ref-law> beziehungsweise es sei ihm vorliegend einzig der Weg der Abänderungsklage offen gestanden (Ziff. 28 der Beschwerde).
Wenn das Obergericht demnach geprüft hat, ob der vorzeitige Eintritt in den Ruhestand durch den Beschwerdeführer einen Abänderungsgrund nach <ref-law> darstellt (vgl. dazu <ref-ruling>), ist nicht ersichtlich, inwiefern es <ref-law> verletzt haben könnte. Die Beschwerde erweist sich insoweit als unbegründet und es braucht damit nicht weiter darauf eingegangen zu werden, ob die widersprüchlichen und teilweise schwer verständlichen Ausführungen des Beschwerdeführers den Begründungsanforderungen von <ref-law> überhaupt zu genügen vermögen.
7. Aus den dargelegten Gründen muss die Beschwerde abgewiesen werden, soweit darauf einzutreten ist. Der Beschwerdeführer wird kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Uri, Zivilrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 16. März 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Bettler