Sachverhalt: A. Am 23. August 2006 schloss A._ (Beschwerdeführer) mit der X._ AG (Beschwerdegegnerin) einen "Bewirtschaftungsvertrag". Darin verpflichtete sich der Beschwerdeführer, im Vertrag einzeln aufgeführte, im Eigentum der Beschwerdegegnerin stehende Appartements und Parkplätze namens und im Auftrag der Beschwerdegegnerin zu vermieten. Unter demselben Datum schloss der Beschwerdeführer mit der Y. Z._ AG, vertreten durch die Beschwerdegegnerin, einen Mietvertrag über das auf der selben Liegenschaft wie die Appartements gelegene Restaurant Y._ in Q._. Ziff. 7.5 des Mietvertrages statuiert, dass die Parteien für die Vermietung der Appartement-Hotel-Zimmer eine separate Dienstleistungs-Vereinbarung treffen. Mit Schreiben vom 19. März 2009 kündigte die Beschwerdegegnerin den Bewirtschaftungsvertrag auf Ende Oktober 2009. B. Am 27. April 2009 beantragte der Beschwerdeführer der Schlichtungsbehörde für Miete und Pacht des Bezirkes Maloja die Durchführung einer Schlichtungsverhandlung und die Feststellung der Ungültigkeit der Kündigung vom 19. März 2009 gemäss Art. 298 Abs. 2 OR. Die Beschwerdegegnerin beantragte nebst der Abweisung des Gesuches namentlich, es sei festzustellen, dass es sich beim Bewirtschaftungsvertrag nicht um einen Pacht- oder Mietvertrag handle. Mit Beschluss vom 17. Juni 2009 stellte die Schlichtungsbehörde fest, dass zwischen den Parteien keine Einigung erzielt werden konnte, und trat auf die Klage des Beschwerdeführers nicht ein. Dieser gelangte an das Bezirksgericht Maloja mit dem Begehren, den Nichteintretensentscheid der Schlichtungsbehörde aufzuheben und die Sache zur Neubeurteilung an diese zurückzuweisen. Eventuell sei die Nichtigkeit der Kündigung vom 19. März 2009 festzustellen. Mit Urteil vom 10. März 2010 trat das Bezirksgericht Maloja auf die Klage nicht ein, im Wesentlichen mit der Begründung, beim Bewirtschaftungsvertrag handle es sich nicht um einen Mietvertrag. Da die Klage gestützt auf Art. 63 ZPO/GR nicht beim Vermittler eingeleitet worden sei und kein Leitschein vorliege, fehle es an einer Prozessvoraussetzung. C. Der Beschwerdeführer focht diesen Entscheid beim Kantonsgericht von Graubünden an. Er beantragte die Aufhebung des bezirksgerichtlichen Urteils und die Rückweisung der Sache zur Neubeurteilung, eventuell die Feststellung der Nichtigkeit der Kündigung vom 19. März 2009. Das Kantonsgericht wies die Beschwerde am 16. November 2010 ab. Auch das Kantonsgericht qualifizierte den Bewirtschaftungsvertrag nicht als Miet- oder Pachtvertrag, sondern als einen Innominatkontrakt, auf welchen die Regeln des einfachen oder eines Sondertyps des Auftrags anwendbar sind (Art. 394 ff. OR bzw. Art. 412 ff. OR). Die Streitsache sei damit zu Unrecht der Schlichtungsbehörde für Miete und Pacht unterbreitet worden. Mangels gehöriger Vermittlung sei das Bezirksgericht zu Recht auf die Klage nicht eingetreten. D. Der Beschwerdeführer beantragt dem Bundesgericht mit Beschwerde in Zivilsachen, das Urteil des Kantonsgerichts Graubünden vom 24. November 2010 aufzuheben und die Nichtigkeit der Kündigung vom 19. März 2009 festzustellen. Eventuell sei das angefochtene Urteil aufzuheben und die Sache zur Neubeurteilung an das Kantonsgericht, subeventuell an das Bezirksgericht Maloja zurückzuweisen. Dem Gesuch um Gewährung der aufschiebenden Wirkung gab das Bundesgericht mit Verfügung vom 25. Januar 2011 statt. Sowohl die Beschwerdegegnerin wie auch das Kantonsgericht schliessen auf Abweisung der Beschwerde, soweit auf sie einzutreten sei.