Sachverhalt: A. Mit Vertrag vom 3./8. September 1999 beauftragte die Stadt Y._ X._ für die Dauer von zehn Jahren mit den Abfallsammeldiensten auf dem Stadtgebiet und dem Transport dieser Abfälle zu den von ihr bestimmten Abladeorten. Per 1. Januar 2004 trat eine Vertragsänderung in Kraft, wonach sich einerseits der Abladeort für die Abfälle änderte und sich andererseits - aufgrund des so entstehenden Mehraufwandes für den Transportunternehmer - die finanziellen Abgeltungen erhöhten. Mit Schreiben vom 26. September 2005 und vom 29. November 2005 kündigte der Stadtrat von Y._ den Vertrag mit X._ vorzeitig. Er berief sich dabei auf eine Vertragsbestimmung, wonach eine einseitige Kündigung bei erheblich veränderten Rahmenbedingungen, welche zu einer unzumutbaren finanziellen Übervorteilung einer Partei führen, möglich sei. B. X._ erachtete die Kündigung des Vertrages als unzulässig und erhob am 10. November 2006 Klage beim Verwaltungsgericht des Kantons Zürich. Darin verlangte er von der Stadt Y._ die Leistung von Schadenersatz in Höhe von Fr. 1'055'198.55 nebst Schadenszins zu 5 % seit dem 1. Mai 2006. Nachdem die Stadt Y._ die Abweisung der Klage beantragt hatte, reduzierte X._ seine Forderung replicando auf Fr. 1'003'936.50. In seinem Urteil vom 10. Juli 2008 erachtete das Verwaltungsgericht die Kündigung des Vertrages durch die Stadt Y._ als rechtens und wies die Klage von X._ vollumfänglich ab. C. Mit Eingabe vom 19. September 2008 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt die Aufhebung des Urteils des Verwaltungsgerichts und die Rückweisung der Sache an die Vorinstanz. Die Stadt Y._ beantragt, es sei auf die Beschwerde nicht einzutreten. Eventualiter sei die Beschwerde abzuweisen und der Entscheid des Verwaltungsgerichts vom 10. Juli 2008 vollumfänglich zu bestätigen. Das Verwaltungsgericht des Kantons Zürich beantragt die Abweisung der Beschwerde.