Sachverhalt: A. A._ (geb. 1983) und B._ (geb. 1979) sind die unverheirateten Eltern von C._ (geb. 2010). Mit Vereinbarung vom 7. März 2011, genehmigt durch die Vormundschaftsbehörde U._ am 8. März 2011, vereinbarten die damals in gemeinsamem Haushalt lebenden Eltern, dass ihnen die elterliche Sorge gemeinsam zustehen soll und sie die Erziehungsverantwortung gemeinsam wahrnehmen; für den Fall der Auflösung der Hausgemeinschaft soll die Obhut der Mutter zustehen und die Aufteilung der Betreuung unter Berücksichtigung der tatsächlichen Lebensverhältnisse im Auflösungszeitpunkt erfolgen. Ferner regelten sie den Kindesunterhalt. Im Sommer 2013 trennten sich die Eltern, nahmen aber in der Folge die Beziehung unter Beibehaltung getrennter Haushalte wieder auf. Ende 2014 trennten sich A._ und B._ erneut. B. Mit Blick auf den von der Mutter geplanten Wegzug mit dem Kind nach Solothurn beantragte der Vater bei der Kindes- und Erwachsenenschutzbehörde (KESB) Oberland Ost sinngemäss, der Mutter sei zu verbieten, den Aufenthaltsort des Kindes von U._ bei Interlaken nach Solothurn zu verlegen, und es sei die Betreuung des Kindes zu regeln, beispielsweise auch im Sinn einer geteilten Obhut. Mit Entscheid vom 17. Februar 2015 wies die KESB die Anträge ab und erteilte B._ gestützt auf Art. 301a ZGB die Zustimmung zum Wechsel des Aufenthaltsortes des Kindes. Sie erwog, dass bei einem Wegzug nach Solothurn ein geteiltes Obhutsrecht keinen Sinn mache; sodann mache es auch keinen Sinn, die Betreuungsanteile zu regeln, weil sich die Eltern darüber sowie hinsichtlich des Besuchsrechts bislang selbst hätten einigen können und zuerst abzuwarten sei, ob dies den Eltern auch für die Zukunft gelinge. Mit Beschwerde vom 19. März 2015 verlangte der Vater die Aufhebung des Entscheides der KESB, die Abweisung des Begehrens der Mutter um Verlegung des Aufenthaltsortes des Kindes sowie die geteilte Obhut für die Eltern, unter Regelung der Betreuungsanteile. Mit Entscheid vom 22. Juni 2015 wies das Obergericht des Kantons Bern die Beschwerde ab. C. Mit Beschwerde in Zivilsachen vom 23. Juli 2015 beantragt A._, die beiden kantonalen Entscheide seien aufzuheben, der Mutter sei die Zustimmung zum Wechsel des Aufenthaltsortes des Kindes nicht zu erteilen und es sei die gemeinsame bzw. alternierende Obhut auszusprechen, unter Regelung der hälftigen Betreuungsanteile; eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Mit Präsidialverfügung vom 5. August 2015 wurde das Gesuch um aufschiebende Wirkung infolge des zwischenzeitlich erfolgten Wegzuges als gegenstandslos abgeschrieben. Mit Schreiben vom 17. März 2016 verzichtete das Obergericht auf eine Vernehmlassung. Mit Vernehmlassungen vom 24. März 2016 und 1. April 2016 schlossen die KESB und die Mutter je auf Abweisung der Beschwerde. Überdies reichten die Eltern am 17. bzw. 29. April 2016 eine Replik und Duplik ein.