Sachverhalt:
A. A.a Der 1961 geborene K._ war als Bauarbeiter der P._ AG tätig und bei der Schweizerischen Unfallversicherungsanstalt (SUVA) gegen Unfallfolgen versichert. Am 27. April 1994 zog er sich bei einem Sprung von einer LKW-Rampe am rechten Fuss eine Abrissfraktur des Os metatarsale V im Bereich der Basis zu. Nach mehreren operativen Eingriffen wurde am 15. Oktober 1998 eine Arthrodese durchgeführt. Die SUVA sprach K._ aufgrund der Befunde am rechten Fuss mit Verfügung vom 27. September 1999 eine Invalidenrente für eine Erwerbsunfähigkeit von 20 % sowie eine Entschädigung für eine Integritätseinbusse von 15 % zu. Mit Einspracheentscheid vom 22. September 2000 bestätigte sie ihre Verfügung. Auf Beschwerde hin wies das Verwaltungsgericht des Kantons Zug mit Entscheid vom 26. September 2002 die Sache an die SUVA zurück, damit diese einen möglichen Kausalzusammenhang zwischen dem Unfallereignis und den inzwischen aufgetretenen Rückenbeschwerden kläre. Das damalige Eidgenössische Versicherungsgericht schützte mit Urteil vom 21. Juli 2003 (U 327/02) den kantonalen Entscheid in diesem Punkt.
A.b In der Folge wurde am 4. Dezember 2003 zunächst eine Aktenbeurteilung bei Dr. med. S._, Facharzt für Chirurgie von der Abteilung Versicherungsmedizin der SUVA, eingeholt. Am 17. August 2005 erstattete Dr. med. U._, Facharzt für Orthopädische Chirurgie, ein medizinisches Gutachten zur Frage der Unfallkausalität der Rückenbeschwerden. Am 25. Oktober 2005 beantwortete er zudem Ergänzungsfragen. Mit Verfügung vom 31. Januar 2006 und Einspracheentscheid vom 8. Juni 2007 verneinte die SUVA eine Leistungspflicht für die Rückenbeschwerden, da kein natürlicher Kausalzusammenhang zwischen diesen und dem Unfallereignis vom 27. April 1994 bestehe.
B. Die hiegegen eingereichte Beschwerde wies das Verwaltungsgericht des Kantons Zug mit Entscheid vom 16. April 2009 ab.
C. Mit Beschwerde lässt K._ die Ausrichtung einer UVG-Rente von 100 % und einer Integritätsentschädigung für das Rückenleiden beantragen.
Während die SUVA und das Verwaltungsgericht des Kantons Zug auf Abweisung der Beschwerde schliessen, verzichtet das Bundesamt für Gesundheit auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Das Bundesgericht prüft grundsätzlich nur die geltend gemachten Rügen; es ist nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu prüfen, wenn diese vor Bundesgericht nicht mehr vorgetragen wurden (<ref-ruling> E. 1.4.1 S. 254).
1.2 Im Beschwerdeverfahren um die Zusprechung oder Verweigerung von Geldleistungen der Militär- oder Unfallversicherung ist das Bundesgericht nicht an die vorinstanzliche Feststellung des rechtserheblichen Sachverhalts gebunden (Art. 97 Abs. 2 und Art. 105 Abs. 3 BGG).
2. Die Vorinstanz hat die Bestimmung über den Anspruch auf Leistungen der Unfallversicherung im Allgemeinen (Art. 6 Abs. 1 UVG [in Verbindung mit Art. 4 ATSG]) und die Grundsätze über den für die Leistungspflicht des Unfallversicherers vorausgesetzten natürlichen Kausalzusammenhang zwischen dem Unfall und dem eingetretenen Schaden (Krankheit, Invalidität, Tod; <ref-ruling> E. 2.1 S. 111 f., 129 V 177 E. 3.1 S. 181 mit Hinweisen) und zur im Weiteren erforderlichen Adäquanz des Kausalzusammenhangs zutreffend dargelegt (<ref-ruling>). Gleiches gilt für die Ausführungen zu den Rückfällen und Spätfolgen (<ref-ruling> E. 2c S. 296), zu dem im Sozialversicherungsrecht geltenden Beweisgrad der überwiegenden Wahrscheinlichkeit (<ref-ruling> E. 9.5 S. 125 mit Hinweis) sowie zur Beweiswürdigung medizinischer Berichte und Gutachten (<ref-ruling> E. 3a S. 352 mit Hinweisen). Darauf wird verwiesen.
3. Streitig und zu prüfen ist, ob ein Kausalzusammenhang zwischen dem Unfallereignis vom 27. April 1994 und den vom Beschwerdeführer geklagten Rückenbeschwerden gegeben ist.
3.1 Das kantonale Gericht hat den natürlichen Kausalzusammenhang zwischen dem Unfallereignis vom 27. April 1994 und den Rückenbeschwerden im Wesentlichen mit Hinweis auf das Gutachten von Dr. med. U._ vom 17. August 2005 verneint.
3.2 Der Beschwerdeführer bestreitet nicht grundsätzlich den Beweiswert des Gutachtens, sondern lässt einwenden, die Vorinstanz habe den Sachverhalt nicht richtig festgestellt und die gesetzlichen Bestimmungen nicht korrekt angewandt. Aus dem Gutachten von Dr. med. U._ vom 17. August 2005 und seiner ergänzenden Stellungnahme vom 25. Oktober 2005 ergäbe sich, dass eine (Teil-)Kausalität zwischen dem Unfallereignis und den Rückenbeschwerden gegeben sei.
4. 4.1 Dr. med. U._, Facharzt für Orthopädische Chirurgie, diagnostizierte in seinem Gutachten vom 17. August 2005 ein chronisches lumbospondylogenes Schmerzsyndrom, einen Status nach mediolateraler Diskushernie L5/S1 links mit freiem Luxat und Segmentdegenerationen L4/5 und L5/S1. Die Rückenprobleme seien seit Mai 1996 aktenkundig. Die ersten Röntgenbilder von 1996 zeigten eine Segmentdegeneration L4/5 und L5/S1. Diese degenerativen Veränderungen hätten 1998, 2000 und 2001 tendenziell etwas zugenommen. Die Progredienz der degenerativen Veränderungen sei auf diesen Aufnahmen nicht derart dramatisch, dass man eine eindeutige Zuordnung zu schädigenden Ereignissen machen könne. Die im April 2001 operierte Diskushernie sei Ausdruck einer vorbestehenden degenerativen Entwicklung der untersten Bandscheibe der LWS gewesen. Das aktuelle Rückenleiden sei nach seiner Beurteilung weder eine direkte noch eine indirekte Folge des Unfalls vom 27. April 1994. Er sei nicht der Ansicht, dass die Verletzung am rechten Fuss und die daraus folgenden operativen Behandlungen zu einer ungünstigen Statik der Wirbelsäule geführt hätten und damit für das Rückenleiden verantwortlich seien. Er halte einen Zusammenhang zwischen dem aktuellen Rückenleiden und dem Unfallereignis höchstens für möglich. Seines Erachtens seien die Rückenbeschwerden einerseits auf die früheren schweren Belastungen im Beruf zurückzuführen und andererseits auf die zunehmende Dekonditionierung des Beschwerdeführers bei länger dauernder unfallbedingter Arbeitsunfähigkeit. Unter Dekonditionierung verstehe er den Verlust an Muskulatur und den Verlust eines adäquaten Trainingszustandes, welcher eintrete, wenn man eine anstrengende Arbeit oder ein anforderungsreiches Training für eine gewisse Zeit nicht mehr ausführen könne. Dies führe zu einem Verlust an Muskelmasse, zu einem Kraftverlust und zu einem Abbau der Leistungsfähigkeit. Eine lange Arbeitsunfähigkeit führe häufig bei Schwerarbeitern zu einem Symptomatischwerden von bereits vorbestehenden abnützungsbedingten degenerativen Störungen von belasteten Skelettstrukturen.
4.2 Der Beschwerdeführer wandte hierzu ein, bei den von Dr. med. U._ gemachten Angaben handle es sich nicht um Wahrscheinlichkeitsgrade, sondern um Teilkausalitäten. Der Gutachter solle angeben, in welchem Ausmass (Prozent von Hundert) die einzelnen Faktoren teilkausal für die Rückenbeschwerden seien. Dr. med. U._ antwortete in einer Stellungnahme vom 25. Oktober 2005, bei einer Aufteilung der Gesamtkausalität in Teilkausalitäten würde er den durch Bauarbeiten vorgeschädigten Vorzustand der Wirbelsäule in der Grössenordnung von 60 % einordnen, die Dekonditionierung mit 30 % und die Fehlhaltung bzw. das Schonhinken mit 10 %. Er hielt jedoch am Ergebnis seines Gutachtens fest und beurteilte die Rückenproblematik nur in einem möglichen Zusammenhang mit der Fussverletzung. Zur Dekonditionierung gab er an, dass diese nicht eigentliche Unfallfolge, sondern eine Folge der Arbeitsunfähigkeit sei. Es gebe sehr gute Statistiken darüber, dass eine schnelle Reintegration von Unfallverletzten in die frühere Arbeit solche Dekonditionierungen mit guten Chancen vermeiden könnten. Eine Dekonditionierung könne man wieder verändern, was mit Unfallfolgen nicht unbedingt möglich sei.
5. 5.1 Aus dem Gutachten von Dr. med. U._ ergibt sich, dass dieser einen Kausalzusammenhang zwischen den Rückenbeschwerden und dem Unfallereignis bzw. dem Schonhinken des Beschwerdeführers als nicht überwiegend wahrscheinlich gegeben beurteilte. Hingegen führte er die Rückenbeschwerden auf die jahrelange schwere Arbeit auf dem Bau einerseits und eine Dekonditionierung durch länger dauernde unfallbedingte Arbeitsunfähigkeit andererseits zurück. An dieser Beurteilung änderte auch die ergänzende Stellungnahme vom 25. Oktober 2005 nichts. Zwar führten die Bemerkungen des Rechtsvertreters des Beschwerdeführers, welcher die Frage nach dem Beweismass durch diejenige nach der Teilkausalität ersetzt haben wollte, zu gewissen Unsicherheiten bei Dr. med. U._, was aus seiner ergänzenden Stellungnahme ersichtlich ist. Dr. med. U._ antwortete entsprechend den Vorgaben der Frage nach dem Umfang der Teilkausalitäten der einzelnen Faktoren und wies dem Vorzustand der Wirbelsäule einen Umfang von 60 %, der durch die Arbeitslosigkeit bedingten Arbeitsunfähigkeit einen Umfang von 30 % und der Fehlhaltung bzw. dem Schonhinken aufgrund der Fussverletzung einen Umfang von ca. 10 % zu. Aus dieser Antwort für sich lässt sich, entgegen der Annahme des Beschwerdeführers, keine rechtserhebliche Teilkausalität der einzelnen Faktoren folgern. Auch eine Teilursache muss überwiegend wahrscheinlich den Schaden bewirkt haben. Dr. med. U._ äussert sich hierbei allerdings nicht über das Beweismass, bzw. ob die einzelnen Faktoren auch überwiegend wahrscheinlich die Rückenbeschwerden verursacht haben. Eine überwiegende Wahrscheinlichkeit des Kausalzusammenhangs ist zwischen dem Vorzustand der Wirbelsäule und der durch die Arbeitsunfähigkeit bedingten Dekonditionierung einerseits und den Rückenbeschwerden andererseits zu bejahen. Dies ergibt sich bereits aus dem eigentlichen Gutachten vom 17. August 2005, in dem Dr. med. U._ die Rückenbeschwerden auf diese beiden Faktoren zurückführte. Für die Fehlhaltung bzw. das Schonhinken aufgrund der Fussverletzung gilt dies jedoch nicht, auch wenn Dr. med. U._ in seiner ergänzenden Stellungnahme (entsprechend der engen Vorgabe der Frage) eine Teilkausalität von ca. 10 % erwähnte. Er selber bezeichnete sowohl im Gutachten als auch an anderer Stelle in der ergänzenden Stellungnahme vom 25. Oktober 2005 einen Kausalzusammenhang zwischen der Fussverletzung und den Rückenbeschwerden lediglich als möglich, nicht jedoch als überwiegend wahrscheinlich. Damit ist die Teilkausalität dieses Faktors nicht im rechtlich notwendigen Ausmass gegeben.
5.2 Die Vorinstanz hat mit Verweis auf die Rechtsprechung argumentiert, es entspreche einer medizinischen Erfahrungstatsache, dass praktisch alle Diskushernien bei Vorliegen degenerativer Bandscheibenveränderungen entstünden und ein Unfallereignis nur ausnahmsweise als eigentliche Ursache in Betracht falle. Gleiches gelte bezüglich der Verschlimmerung einer vorbestehenden Diskushernie. Sie übersieht hierbei jedoch, dass sich diese medizinische Erfahrungstatsache auf Fälle bezieht, bei denen die Wirbelsäule durch das Unfallereignis direkt betroffen ist bzw. die Rückenbeschwerden in unmittelbarer zeitlicher Nähe zum Unfallereignis aufgetreten sind (vgl. etwa RKUV 2000 Nr. U 379 S. 192, U 138/99 E. 2a; Urteil des Eidgenössischen Versicherungsgerichts U 354/04 vom 11. April 2005 E. 2.2, mit Hinweis auf die medizinische Literatur und Urteil des Bundesgerichts 8C_326/2008 vom 24. Juni 2008 E. 3). Vorliegend war die Wirbelsäule durch das Unfallereignis vom 27. April 1994 weder betroffen noch lagen während zwei Jahren nach dem Unfall Rückenbeschwerden vor. Hingegen können unfallbedingte Fuss- und Beinverletzungen, Beinlängenverkürzungen usw. zu Fehlbelastungen führen, die als indirekte Unfallfolgen später zu unfallkausalen Rückenbeschwerden führen (RKUV 2003 Nr. U 487 S. 337, U 38/01; Urteile des Bundesgerichts U 522/06 vom 12. Oktober 2007 E. 5.2 und U 246/06 vom 5. Januar 2007 E. 4.3, je mit Hinweisen; Urteil des Eidgenössischen Versicherungsgerichts U 415/05 vom 26. April 2006 E. 3.2). Dies muss allerdings im Einzelfall medizinisch abgeklärt werden, was Dr. med. U._ tat. Er kam dabei zum Schluss, ein Kausalzusammenhang zwischen der Fehlhaltung bzw. dem Schonhinken und den Rückenbeschwerden sei nicht überwiegend wahrscheinlich gegeben.
5.3 Zu beurteilen bleibt, ob eine Teilkausalität zwischen dem Unfallereignis und den Rückenbeschwerden gestützt auf die lang dauernde Arbeitsunfähigkeit mit der dabei eingetretenen Dekonditionierung zu bejahen ist. Die Arbeitsunfähigkeit wurde durch die Abrissfraktur des Os metatarsale anlässlich des Unfallereignisses vom 27. April 1994 und die anschliessende Behandlung bzw. Folgeoperationen begründet. Das Unfallereignis war somit Ursache für die Arbeitsunfähigkeit. Zwar weist Dr. med. U._ kritisch darauf hin, der Beschwerdeführer habe immer wieder darauf gedrängt, operiert zu werden. Dadurch seien die Wiedereingliederungsbemühungen gebremst worden. Indes erachteten die Ärzte die Folgebehandlung/-operationen als medizinisch indiziert. Auch diese stellten Unfallfolgen dar und wurden von der SUVA unbestritten übernommen. Eine Unterbrechung des Kausalzusammenhangs kann aus dem Verhalten des Beschwerdeführers daher nicht gefolgert werden. Wenn der Gutachter in der ergänzenden Stellungnahme die Auffassung äussert, die Arbeitsunfähigkeit sei der Grund für die Dekonditionierung und nicht das Unfallereignis, so übersieht er, dass massgebende Ursachen im Rahmen des natürlichen Kausalzusammenhangs alle Umstände sind, ohne deren Vorhandensein die gesundheitliche Beeinträchtigung nicht oder nicht in gleicher Weise oder nicht zur gleichen Zeit eingetreten wäre. Ein natürlicher Kausalzusammenhang ist gegeben, sobald der Unfall nicht weggedacht werden kann, ohne dass auch die eingetretene gesundheitliche Störung entfiele (Conditio sine qua non; <ref-ruling> E. 3.1 S. 181, 402 E. 4.3.1 S. 406 mit Hinweisen). Auch Kausalketten sind beim natürlichen Kausalzusammenhang grundsätzlich zu berücksichtigen. Der Umstand, dass ein alternativer Faktor wie eine länger dauernde Arbeitslosigkeit aus nicht-medizinischen (etwa konjunkturellen) Gründen ebenfalls zur Dekonditionierung und damit zum Symptomatischwerden der degenerativen Befunde im Rückenbereich geführt hätte, spricht nicht gegen den Kausalzusammenhang. Nach der Rechtsprechung gehören zu den im Sinne von Art. 6 Abs. 1 UVG massgebenden Ursachen auch Umstände, ohne deren Vorhandensein die gesundheitliche Beeinträchtigung nicht zur gleichen Zeit eingetreten wäre. Eine schadenauslösende traumatische Einwirkung wirkt also selbst dann leistungsbegründend, wenn der betreffende Schaden auch ohne das versicherte Ereignis später wohl eingetreten wäre, der Unfall somit nur hinsichtlich des Zeitpunkts des Schadenseintritts Conditio sine qua non war. Anders verhält es sich, wenn der Unfall nur Gelegenheits- oder Zufallsursache ist, welche ein gegenwärtiges Risiko, mit dessen Realisierung jederzeit zu rechnen gewesen wäre, manifest werden lässt, ohne im Rahmen des Verhältnisses von Ursache und Wirkung eigenständige Bedeutung anzunehmen (Urteil 8C_301/2007 vom 15. Januar 2008 mit Hinweis auf SVR 2007 UV Nr. 28 S. 94, U 413/05 E. 4.2). Vorliegend stellt das Unfallereignis keine Gelegenheits- oder Zufallsursache dar. Die lange Arbeitsunfähigkeit des Beschwerdeführers steht in einer Kausalkette zwischen dem Unfallereignis und der Dekonditionierung mit dem Symptomatischwerden der Rückenbeschwerden. Die Adäquanz des Kausalzusammenhangs ist dabei ebenfalls zu bejahen.
5.4 Die SUVA argumentiert, der Beschwerdeführer hätte im Rahmen seiner Schadenminderungspflicht mittels aktiver Rückentherapie der Dekonditionierung seiner Rückenmuskulatur entgegenwirken können. Hierbei ist allerdings zu beachten, dass sich während der ersten beiden Jahre nach dem Unfallereignis noch gar keine Rückenbeschwerden gezeigt hatten, der Beschwerdeführer somit zunächst keine Veranlassung hatte, ein entsprechendes Training durchzuführen. Danach hätte die SUVA den Beschwerdeführer im Rahmen eines Mahn- und Bedenkzeitverfahrens gemäss Art. 48 Abs. 2 aUVG (in der bis 31. Dezember 2002 gültig gewesenen Fassung) bzw. gemäss Art. 21 Abs. 4 ATSG auffordern müssen, die entsprechenden Therapien zu besuchen, um (bei Nichtbefolgung) wegen Verstosses gegen die Schadenminderungspflicht die Leistungen einzustellen (vgl. <ref-ruling>). Aus den Akten sind jedoch weder von den behandelnden Ärzten noch von der SUVA Aufforderungen zum Rückentraining ersichtlich, welchen der Beschwerdeführer nicht nachgekommen wäre.
5.5 Zusammenfassend ist gestützt auf das Gutachten vom 17. August 2005 und die ergänzende Stellungnahme vom 25. Oktober 2005 eine Teilkausalität zwischen dem Unfallereignis vom 27. April 1994 und den Rückenbeschwerden aufgrund der unfallkausalen langen Arbeitsunfähigkeit und der dabei erfolgten Dekonditionierung überwiegend wahrscheinlich gegeben.
6. Dr. med. U._ verwies bei seinen Ausführungen zur Dekonditionierung auf den Verlust an Muskelmasse, den Kraftverlust und den Abbau der Leistungsfähigkeit. Er gab auch an, eine Dekonditionierung könne man wieder verändern, was mit Unfallfolgen nicht immer möglich sei. Zur Frage nach angemessenen Therapiemöglichkeiten und zur zumutbaren Arbeitsfähigkeit nahm er allerdings keine Stellung. Die Prüfung eines allfälligen Anspruches auf Invalidenrente und Integritätsentschädigung ist bei dieser Aktenlage nicht möglich. Eine Bindung der Unfallversicherung an die Beurteilung der Invalidenversicherung besteht nicht (<ref-ruling>). Die Sache ist daher an die SUVA zurückzuweisen, damit sie insbesondere diese Fragen medizinisch abklären lässt. Sollten sich die Dekonditionierung, welche für sich allein betrachtet keine Diagnose mit Krankheitswert darstellt, bzw. die dadurch verursachten Rückenbeschwerden nicht mehr beheben lassen, hat sie zudem eine medizinische Beurteilung des Integritätsschadens vornehmen zu lassen. Hernach hat sie über den Leistungsanspruch des Beschwerdeführers neu zu verfügen.
7. Die Gerichtskosten werden der unterliegenden SUVA auferlegt (Art. 66 Abs. 1 BGG; <ref-ruling>, 132 V 215 E. 6.1 E. 235). Sie ist gegenüber dem anwaltlich vertretenen Beschwerdeführer entschädigungspflichtig (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird in dem Sinne gutgeheissen, dass der Entscheid des Verwaltungsgerichts des Kantons Zug vom 16. April 2009 und der Einspracheentscheid der Schweizerischen Unfallversicherungsanstalt (SUVA) vom 8. Juni 2007 aufgehoben werden. Die Sache wird an die SUVA zurückgewiesen, damit sie, nach erfolgter Abklärung im Sinne der Erwägungen, über den Leistungsanspruch neu verfüge.
2. Die Gerichtskosten von Fr. 750.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Verwaltungsgericht des Kantons Zug zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Zug, Sozialversicherungsrechtliche Kammer, und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 28. Juli 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Kathriner