Sachverhalt:
A. X._ ist Eigentümer der mit einem Wohnhaus überbauten Parzelle Nr. 417 sowie der östlich daran anschliessenden Parzelle Nr. 930 in der Gemeinde Y._, Gebiet B._. Auf der Parzelle Nr. 930 befand sich ein Stall, den X._ in eine Werkstatt mit darüberliegender Wohnung umbauen wollte. Ein entsprechendes Baugesuch vom 21. Januar 2007 wurde vom Gemeindevorstand der Gemeinde Y._ am 21. bzw. 24. August 2007 abgewiesen. Eine von X._ dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden am 13. bzw. 17. Dezember 2007 ab.
B. Bereits am 1. Oktober 2007 reichte X._ ein Projektänderungsgesuch ein, welches vom Gemeindevorstand am 30. Oktober 2007 unter Auflagen bewilligt wurde. Am 21. Mai 2008 teilte die Gemeinde X._ mit, es sei festgestellt worden, dass er vom bewilligten Bauprojekt abweiche. Sie ordnete einen sofortigen Baustopp an und gab X._ Gelegenheit zur Stellungnahme. X._ bestritt, abweichend zur Bewilligung gebaut zu haben, und stellte eine ausführliche Stellungnahme in Aussicht. Am 25. Juni 2009 wurde X._ erneut zur Stellungnahme eingeladen, nachdem bis zu diesem Zeitpunkt weder eine Stellungnahme noch neue Pläne eingereicht worden waren.
C. Am 27. August 2009 teilte die Gemeinde X._ mit, sie habe anlässlich einer Baukontrolle festgestellt, dass der ausgeführte Bau nicht den genehmigten Plänen gemäss Bewilligung vom 30. Oktober 2007 entspreche, sondern dem nicht genehmigten Baugesuch vom 21. Januar 2007. X._ habe bei Z._, dem Eigentümer der benachbarten Parzelle Nr. 1055, ein Näherbaurecht einzuholen. Erhalte er kein Näherbaurecht, müsse er bis zum 2. Oktober 2009 Pläne einreichen, aus denen ersichtlich sei, wie er den Bau in den rechtmässigen Zustand versetzen wolle. Die Einleitung eines Bussverfahrens wurde vorbehalten. Nachdem X._ erklärte, er sei mit diesem Vorgehen nicht einverstanden, versuchte die Gemeinde die Angelegenheit unter Einbezug von Z._ einvernehmlich zu lösen, was letztlich nicht gelang.
D. Am 21. bzw. 22. September 2010 verfügte der Gemeindevorstand, X._ habe die Baute auf der Parzelle Nr. 930 auf das Mass gemäss Baubewilligung vom 30. Oktober 2007 zurückzuführen. Hierzu werde ihm eine Frist bis zum 31. Dezember 2010 gewährt. Falls er diese Frist nicht einhalte, werde die Gemeinde auf seine Kosten einen Dritten beauftragen. X._ wurden eine Busse von Fr. 1'000.-- sowie die Verfahrenskosten von insgesamt Fr. 8'027.40 auferlegt.
E. Eine von X._ gegen die Verfügung des Gemeindevorstands erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden am 8. Februar 2011 ab.
F. Gegen den Entscheid des Verwaltungsgerichts gelangt X._ mit Beschwerde vom 20. Juni 2011 ans Bundesgericht. Er beantragt die Aufhebung des angefochtenen Entscheids. Mit Verfügung vom 20. Juli 2011 hat das Bundesgericht der Beschwerde aufschiebende Wirkung beigelegt.
G. Die Vorinstanz beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die Gemeinde Y._ beantragt die Abweisung der Beschwerde. Z._ liess sich nicht vernehmen.

Erwägungen:
1. Das angefochtene Urteil des Verwaltungsgerichts ist ein letztinstanzlicher kantonaler Endentscheid in einer öffentlich-rechtlichen Angelegenheit (vgl. Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Der Beschwerdeführer ist als Adressat des angefochtenen Entscheids und als direkt Betroffener zur Beschwerde legitimiert (vgl. <ref-law>). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde vorbehältlich rechtsgenügender Rügen (vgl. Art. 42 Abs. 2 i.V.m. <ref-law>) einzutreten.
2. Der Beschwerdeführer rügt, die Vorinstanz habe den Sachverhalt falsch bzw. nicht vollständig und damit unrichtig im Sinne von <ref-law> festgestellt.
2.1 Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Abs. 2). Von der beschwerdeführenden Person kann die Feststellung des Sachverhalts wiederum nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich (<ref-law>) ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Eine entsprechende Rüge ist substanziiert vorzubringen (<ref-law> i.V.m. <ref-law>).
2.2 Der Beschwerdeführer bringt vor, er sei stark gehbehindert. Er müsse sich im Rollstuhl bewegen und könne keine Absätze oder Treppen mehr besteigen, weshalb er auf ein rollstuhlgängiges Haus angewiesen sei. Zum Beweis verweist er auf zwei schon vor der Vorinstanz eingereichte Kostengutsprachen der IV-Stelle des Kantons Graubünden. Der verlangte Rückbau würde das ganze Vorhaben, das Haus rollstuhlgängig zu machen und insbesondere einen Lift einzubauen, in Frage stellen.
Der Beschwerdeführer hat bereits vor der Vorinstanz vorgebracht, mit der im ersten Baugesuch vom 21. Januar 2007 vorgesehenen Verringerung der Dachneigung sei ein Lifteinbau für eine rollstuhlgängige Wohnung möglich geworden. Sinngemäss hat er im vorinstanzlichen Verfahren auch geltend gemacht, er sei auf eine rollstuhlgängige Wohnung angewiesen. Inwiefern die Vorinstanz in dieser Hinsicht entscheidwesentliche Tatsachen offensichtlich unrichtig im Sinne von <ref-law> festgestellt hätte, wird vom Beschwerdeführer vor Bundesgericht allerdings nicht substanziiert vorgebracht und ist nicht ersichtlich. Aus dem vorinstanzlichen Entscheid wird vielmehr klar, dass der Einwand des Beschwerdeführers, er sei auf eine rollstuhlgängige Wohnung angewiesen, welche mit dem Umbau ermöglicht worden sei, nicht entscheidwesentlich war. Auf die Frage, ob die Vorinstanz auf Grund dieses Einwands hätte anders entscheiden müssen, ist im Rahmen der Prüfung der materiellen Rügen des Beschwerdeführers noch einzugehen (vgl. E. 3.5.3).
2.3 Die Vorinstanz hat im angefochtenen Entscheid festgehalten, die Gemeinde habe versucht, die Angelegenheit unter Einbezug des Eigentümers des benachbarten Grundstücks einvernehmlich zu lösen, was nicht gelungen sei. Die Einigungsgespräche betreffend Einräumung eines Näher- und Grenzbaurechts zugunsten der Parzelle des Beschwerdeführers seien offensichtlich gescheitert. Der Beschwerdeführer bezeichnet diese Feststellungen als aktenwidrig und willkürlich. Er verweist auf eine bereits vor der Vorinstanz eingereichte Aktennotiz der Gemeinde Y._ zu einer Besprechung vom 3. Dezember 2009. Daraus gehe hervor, dass ihm der Eigentümer des benachbarten Grundstücks die Kosten eines Rückbaus habe ersparen wollen. Dieser habe nämlich selber vorgeschlagen, die Mehr- und Minderwerte der betroffenen Liegenschaften schätzen zu lassen. Es sei vereinbart worden, im Anschluss an die Schätzung eine neue Sitzung einzuberufen. Im Falle einer Einigung habe der Eigentümer des benachbarten Grundstücks die Erteilung eines Näherbaurechts in Aussicht gestellt. Die Gemeinde sei mit diesem Vorgehen einverstanden gewesen. Nachdem die von der Gemeinde in Auftrag gegebenen Schätzungen erstellt worden seien, sei aber nichts mehr geschehen. Die Gemeinde habe keine weiteren Anstrengungen unternommen, damit es zwischen ihm und dem Eigentümer des benachbarten Grundstücks zu einer Einigung komme. Stattdessen sei am 21. bzw. 22. September 2010 verfügt worden, dass das Gebäude auf die bewilligten Masse gemäss Baubewilligung vom 30. Oktober 2007 reduziert werden müsse. Eine Lösung, wie sie anlässlich der Besprechung vom 3. Dezember 2009 vorgezeichnet worden sei, sei noch realisierbar.
Wie den Akten zu entnehmen ist, hat die Gemeinde den Beschwerdeführer und den Eigentümer des benachbarten Grundstücks am 5. Februar 2010 über das Ergebnis der in Auftrag gegebenen Schätzungen informiert, beide aufgefordert, die Bewertung zu besprechen und die Gemeinde bis am 19. Februar 2010 zu informieren. Nachdem die Gemeinde innert dieser Frist nicht informiert worden war, richtete sie sich am 18. März 2010 erneut an den Beschwerdeführer und setzte ihm eine letzte Frist zur Stellungnahme bis zum 2. April 2010, welche ebenfalls unbenutzt verstrich. Unter diesen Umständen ist nicht einzusehen, inwiefern die Feststellung der Vorinstanz, die Gemeinde habe versucht, die Angelegenheit unter Einbezug des Eigentümers des benachbarten Grundstücks einvernehmlich zu lösen, was nicht gelungen sei, offensichtlich unrichtig im Sinne von <ref-law> sein sollte. Das Gleiche gilt für die Feststellung, die Einigungsgespräche betreffend Einräumung eines Näher- und Grenzbaurechts zugunsten des Grundstücks des Beschwerdeführers und zulasten der benachbarten Parzelle seien offensichtlich gescheitert.
2.4 Soweit der Beschwerdeführer darüber hinaus den Verfahrenslauf aus eigener Sicht schildert und er dabei von den tatsächlichen Feststellungen der Vorinstanz abweicht oder diese erweitert, erhebt er keine hinreichend begründete Sachverhaltsrüge. Es besteht insofern kein Anlass, vom Sachverhalt abzuweichen, den die Vorinstanz festgestellt hat.
3. Der Beschwerdeführer bestreitet nicht, den Umbau im Wesentlichen nach dem ursprünglichen rechtskräftig verweigerten Baugesuch vom 21. Januar 2007 ausgeführt zu haben. Wie die Vorinstanz festgestellt hat, weist der errichtete Bau gegenüber dem am 30. Oktober 2007 genehmigten Projekt insbesondere eine geringere Dachneigung auf. Während für den unteren Teil der Baute in den ursprünglichen Gebäudemassen wegen des kantonalrechtlichen Hofstattrechts die Unterschreitung des Grenzabstands gegenüber der Nachbarparzelle nicht von Belang ist, wäre die mit der geringeren Dachneigung verbundene Dachaufstockung gemäss kantonalem Recht nur zulässig, wenn der Nachbar der Grenzabstandsverletzung ausdrücklich zugestimmt hätte und eine entsprechende Anmerkung im Grundbuch eingetragen worden wäre. Dies wird vom Beschwerdeführer ebenfalls nicht bestritten. Er akzeptiert sodann ausdrücklich die wegen der Verletzung der Bauvorschriften von der Gemeinde verfügte und von der Vorinstanz bestätigte Busse. Der Beschwerdeführer bringt aber vor, die Anordnung, wonach er die Baute auf das Mass gemäss Baubewilligung vom 30. Oktober 2007 zurückzuführen habe, andernfalls die Gemeinde auf seine Kosten einen Dritten damit beauftragen werde, sei willkürlich sowie unverhältnismässig und stelle einen ungerechtfertigten Eingriff in seine Eigentumsrechte dar.
3.1 Eine Eigentumsbeschränkung ist nur zulässig, wenn sie auf einer gesetzlichen Grundlage beruht, im öffentlichen Interesse liegt und verhältnismässig ist (<ref-law>). Das Verhältnismässigkeitsprinzip besagt, dass die Grundrechtseinschränkung zur Erreichung des angestrebten Ziels geeignet und erforderlich sein muss und dem Betroffenen in Anbetracht der Schwere der Grundrechtseinschränkung zumutbar ist. Das Vorliegen eines öffentlichen Interesses und die Verhältnismässigkeit prüft das Bundesgericht bei der Beschränkung von Grundrechten frei (<ref-ruling> E. 4.4.1 S. 204 mit Hinweisen).
3.2 Im Falle einer nicht den Bauvorschriften bzw. der Baubewilligung entsprechenden Baute kann die Wiederherstellung des rechtmässigen Zustands unterbleiben, wenn die Abweichung vom Erlaubten nur unbedeutend ist oder die Wiederherstellung nicht im öffentlichen Interesse liegt, ebenso, wenn der Bauherr in gutem Glauben angenommen hat, die von ihm ausgeübte Nutzung stehe mit der Baubewilligung im Einklang, und ihre Fortsetzung nicht schwerwiegenden öffentlichen Interessen widerspricht (<ref-ruling> E. 6 S. 35; <ref-ruling> E. 6 S. 221 mit Hinweisen). Auf die Verhältnismässigkeit berufen kann sich auch ein Bauherr, der nicht gutgläubig gehandelt hat. Er muss aber in Kauf nehmen, dass die Behörden aus grundsätzlichen Erwägungen, namentlich zum Schutz der Rechtsgleichheit und der baulichen Ordnung, dem Interesse an der Wiederherstellung des gesetzmässigen Zustands erhöhtes Gewicht beimessen und die dem Bauherrn allenfalls erwachsenden Nachteile nicht oder nur in verringertem Masse berücksichtigen (<ref-ruling> E. 6.4 S. 39 f.; <ref-ruling> E. 6b S. 224).
3.3 Gesetzliche Grundlage für die von der Vorinstanz bestätigte Anordnung, wonach der Beschwerdeführer die Baute auf das Mass gemäss Baubewilligung vom 30. Oktober 2007 zurückzuführen habe, bildet Art. 94 Abs. 1 und 3 des Raumplanungsgesetzes für den Kanton Graubünden vom 6. Dezember 2004, wonach materiell vorschriftswidrige Zustände auf Anordnung der zuständigen Behörde vom Eigentümer bzw. von Personen, die den rechtswidrigen Zustand herbeigeführt haben, zu beseitigen sind. Die umstrittene Anordnung zur Wiederherstellung des rechtmässigen Zustands soll die rechtsgleiche Anwendung und Durchsetzung der Bauvorschriften sicherstellen. Sie stellt eine im öffentlichen Interesse liegende, hierfür geeignete Massnahme dar.
3.4 Der Beschwerdeführer wendet ein, der gesetzesmässige Zustand lasse sich auch damit wieder herstellen, dass ein Näherbaurecht vereinbart werde. Eine solche Lösung sei von der Gemeinde selber aufgezeigt worden. Die Einräumung eines Näherbaurechts stelle eine mildere Massnahme dar als der verfügte Rückbau, zumal die ihm anfallenden Kosten für die Einräumung eines Näherbaurechts wesentlich geringer seien. Der Beschwerdeführer bringt nicht vor, dass die Gemeinde ein Näherbaurecht zugunsten seines Grundstücks und zulasten der Parzelle des Nachbars hoheitlich hätte anordnen müssen. Ein solches Vorgehen wäre denn mit den Rechten des Eigentümers des benachbarten Grundstücks auch nicht vereinbar. Der Beschwerdeführer ist aber der Ansicht, die Gemeinde hätte mehr dafür tun müssen, dass es hinsichtlich der Einräumung eines Näherbaurechts zu einer Einigung zwischen dem Eigentümer des benachbarten Grundstücks und ihm gekommen wäre.
Entgegen der Ansicht des Beschwerdeführers war die Gemeinde nicht verpflichtet, selber aktiv auf eine Einigung zwischen dem Eigentümer des benachbarten Grundstücks und dem Beschwerdeführer hinzuwirken. Vielmehr hat sie dem Verhältnismässigkeitsprinzip schon in ausreichender Weise Genüge getan, indem sie dem Beschwerdeführer - bevor sie die Wiederherstellung des rechtmässigen Zustands anordnete - Gelegenheit gab, sich mit dem Eigentümer des benachbarten Grundstücks zu einigen und mit ihm ein Näherbaurecht zu vereinbaren. Darüber hinaus hat sie die Betroffenen gar zu einem Gespräch eingeladen, die Mehr- und Minderwerte der betroffenen Liegenschaften schätzen lassen, den Beschwerdeführer und den Eigentümer des benachbarten Grundstücks über das Ergebnis der Berechnung informiert, beide aufgefordert, die Bewertung zu besprechen und die Gemeinde zu informieren und dem Beschwerdeführer schliesslich eine letzte Frist zur Stellungnahme gesetzt, welche unbenutzt verstrich. Die Gemeinde war, bevor sie die Wiederherstellung des rechtmässigen Zustands anordnete, nicht gehalten, noch mehr dafür zu tun, dass es hinsichtlich der Einräumung eines Näherbaurechts zu einer Einigung zwischen dem Eigentümer des benachbarten Grundstücks und dem Beschwerdeführer kommt. Eine für den Beschwerdeführer mildere Massnahme, welche im Hinblick auf den angestrebten Erfolg ebenso geeignet wäre, ist somit nicht ersichtlich.
3.5 Zu prüfen bleibt, ob die Einschränkung in die Eigentumsgarantie für den Beschwerdeführer in Anbetracht ihrer Schwere zumutbar ist.
3.5.1 Der Beschwerdeführer bringt zu Recht nicht vor, die Abweichung von der erteilten Bewilligung sei nur unbedeutend. Er bestreitet aber, den unrechtmässigen Zustand bösgläubig herbeigeführt zu haben.
Wie die Vorinstanz im angefochtenen Entscheid zu Recht festgehalten hat, war dem Beschwerdeführer bewusst, dass er sein ursprüngliches Projekt gemäss Baugesuch vom 21. Januar 2007 nicht verwirklichen darf, nachdem das Baugesuch mit dem Urteil des Verwaltungsgerichts vom 13. bzw. 17. Dezember 2007 rechtskräftig abgewiesen worden war. Daran ändert auch der Umstand nichts, dass der Eigentümer des benachbarten Grundstücks zunächst erhobene privatrechtliche Baueinsprachen zurückgezogen und dem Beschwerdeführer für die Bauzeit die temporäre Nutzung eines Landstreifens seiner Parzelle sowie ein Durchgangsrecht eingeräumt hat. Indem der Beschwerdeführer in der Folge nicht nach dem bewilligten Projektänderungsgesuch vom 1. Oktober 2007, sondern im Wesentlichen nach dem abgewiesenen Baugesuch vom 21. Januar 2007 gebaut hat, hat er den unrechtmässigen Zustand bösgläubig herbeigeführt. Soweit er geltend macht, er habe sich darauf verlassen, dass er sich mit dem Eigentümer des benachbarten Grundstücks später auf ein Näherbaurecht würde einigen können, ändert dies nichts daran, dass er nicht in gutem Glauben annehmen konnte, der Umbau stehe mit der Baubewilligung im Einklang. Dem öffentlichen Interesse an der Wiederherstellung des gesetzmässigen Zustands ist demzufolge aus grundsätzlichen Erwägungen, namentlich zum Schutz der Rechtsgleichheit und der baulichen Ordnung, erhöhtes Gewicht beizumessen.
3.5.2 Was den Interessengegensatz anbelangt, wirft der Beschwerdeführer der Vorinstanz vor, sie habe nicht berücksichtigt, dass der angeordnete Rückbau sehr teuer zu stehen käme. Die Kosten für den Rückbau seien vom Eigentümer des benachbarten Grundstücks auf Fr. 300'000.-- geschätzt worden. Diese Aufwendungen mit allen persönlichen und gesundheitlichen Folgen könnten ihm nicht zugemutet werden.
Dass Rückbauaufwendungen rein wirtschaftlich gesehen als sinnlos erscheinen mögen, ist unter den gegebenen Umständen kein schlüssiges Argument gegen die Anordnung der Wiederherstellung des rechtmässigen Zustands. Die Verhältnismässigkeit einer Anordnung, widerrechtlich erstellte Objekte zurückzubauen, einseitig von wirtschaftlichen Überlegungen abhängig zu machen, liefe im Ergebnis auf eine starke Relativierung rechtskräftiger Baubewilligungen hinaus (vgl. Urteil 1C_262/2009 vom 14. April 2010 E. 5.4.3).
3.5.3 Was den Einwand des Beschwerdeführers angeht, er sei auf eine rollstuhlgängige Wohnung angewiesen, welche mit dem Umbau ermöglicht worden sei, ist darauf hinzuweisen, dass auch das am 30. Oktober 2007 bewilligte Projekt den Einbau eines Lifts vorsah. Wie aus den in den Akten liegenden Plänen und Fotografien weiter hervorgeht, war das Obergeschoss von der Projektänderung nur leicht betroffen, wobei immerhin der Balkon weggefallen wäre. Zwar hätte sich schliesslich die im Estrichgeschoss entgegen den genehmigten Plänen errichtete Galerie nicht verwirklichen lassen. Wie den Plänen und Fotografien jedoch zu entnehmen ist, ist der nun errichtete Estrich bzw. die Galerie ohnehin nicht mit dem Lift, sondern nur über eine Treppe erreichbar. Es zeigt sich, dass das am 30. Oktober 2007 bewilligte Projekt einen rollstuhlgängigen Ausbau der Wohnung jedenfalls nicht verunmöglicht hätte.
3.5.4 Angesichts der Bösgläubigkeit des Beschwerdeführers in Bezug auf die Herbeiführung des unrechtmässigen Zustands, der nicht unerheblichen Abweichung vom Erlaubten und des hoch zu gewichtenden öffentlichen Interesses am Schutz der Rechtsgleichheit und der baulichen Ordnung erweist sich die durch die Anordnung der Wiederherstellung des rechtmässigen Zustands ergebende Einschränkung in die Eigentumsrechte der Beschwerdeführer als zumutbar.
3.6 Damit steht fest, dass die Gemeinde die Wiederherstellung des rechtmässigen Zustands anordnen durfte, ohne damit ungerechtfertigterweise in die Eigentumsrechte des Beschwerdeführers einzugreifen oder gegen den Grundsatz der Verhältnismässigkeit zu verstossen. Wie aus den vorstehenden Erwägungen ersichtlich wird, ist der angefochtene Entscheid auch nicht offensichtlich unhaltbar, steht er nicht zur tatsächlichen Situation in klarem Widerspruch, verletzt er nicht eine Norm oder einen unumstrittenen Rechtsgrundsatz krass und läuft er nicht in stossender Weise dem Gerechtigkeitsgedanken zuwider. Eine Verletzung von <ref-law> ist deshalb ebenfalls zu verneinen (vgl. <ref-ruling> E. 2.4 S. 5).
4. Die Beschwerde erweist sich als unbegründet und ist abzuweisen. Die Gemeinde Y._ wird dem Beschwerdeführer eine neue Frist zur Wiederherstellung des rechtmässigen Zustands anzusetzen haben. Bei diesem Ausgang trägt der Beschwerdeführer die Gerichtskosten (vgl. <ref-law>). Die in ihrem amtlichen Wirkungskreis obsiegende Gemeinde hat keinen Anspruch auf eine Parteientschädigung (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Gemeinde Y._, dem weiteren Beteiligten und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 25. November 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Mattle