Sachverhalt: A. X._ war seit 1. Oktober 1996 als Geschäftsführer des Verbands Y._ tätig. Nachdem dessen Präsident am 27. März 2008 von einer Sachbearbeiterin auf Führungsdefizite aufmerksam gemacht worden war, welche am 3. April 2008 durch eine weitere Sachbearbeiterin bestätigt wurden, beauftragte er die externe Beratungsstelle Z._ mit der Überprüfung der personellen Situation auf der Geschäftsstelle. Im Gutachten vom 26. Mai 2008 zeigte diese gravierende Mängel in der Geschäftsführung, der Führung der Mitarbeitenden und im Engagement von X._ auf. Dies wurde ihm anlässlich der Sitzung mit Vertretern des Vorstandes des Verbandes Y._ vom 12. Juni 2008 mündlich eröffnet. Dazu und zur vom Vorstand ins Auge gefassten Kündigung des Anstellungsverhältnisses konnte er sich am 10. Juli 2008 auch schriftlich äussern. Mit Schreiben vom 14. Juli 2008 kündigte der Verband Y._ das Arbeitsverhältnis auf den 31. Januar 2009, unter sofortiger Freistellung von der Arbeitsleistung. Zur Begründung verwies er auf die ungenügenden Leistungen als Geschäftsführer und Verletzungen gesetzlicher oder vereinbarter Pflichten. B. X._ erhob gegen die Kündigung Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dabei beantragte er die Aufhebung der rechtswidrig erfolgten Kündigung unter sofortiger Wiedereinstellung und eventualiter eine Entschädigung von sechs Monatslöhnen. Mit Entscheid vom 10. Februar 2009 wies das Verwaltungsgericht die Beschwerde ab. C. Mit Beschwerde lässt X._ beantragen, es sei der vorinstanzliche Entscheid aufzuheben und die Rechtsmissbräuchlichkeit der Kündigung festzustellen. Zudem sei ihm eine zwei Monatslöhnen entsprechende Entschädigung von insgesamt Fr. 21'792.30 oder eine Entschädigung nach Ermessen des Gerichts zuzusprechen. Eventuell sei die Sache zur neuerlichen Abklärung und Beurteilung an die Vorinstanz zurückzuweisen. Der Verband Y._ schliesst auf Abweisung der Beschwerde. 