Sachverhalt: A. A._ wurde mit Entscheid der 1. Strafkammer des Obergerichts des Kantons Bern vom 15. Oktober 2014 unter anderem der mehrfachen schweren Körperverletzung schuldig gesprochen und zu einer Freiheitsstrafe von drei Jahren verurteilt. Zudem wurden eine stationäre therapeutische Massnahme nach Art. 59 StGB und eine stationäre Suchtbehandlung nach Art. 60 StGB angeordnet. Eine von A._ dagegen erhobene Beschwerde wies das Bundesgericht mit Urteil 6B_43/2015 vom 18. Mai 2015 ab. Mit Verfügung vom 12. Oktober 2015 wies die Abteilung Straf- und Massnahmenvollzug (ASMV) der Polizei- und Militärdirektion des Kantons Bern A._ zum Vollzug der stationären therapeutischen Massnahme in die Justizvollzugsanstalt Solothurn ein. Wenige Tage später, am 23. Oktober 2015, wurde A._ in Anwendung von Art. 10 lit. g und Art. 30 Abs. 2 des Gesetzes des Kantons Bern vom 25. Juni 2003 über den Straf- und Massnahmenvollzug (SMVG; BSG 341.1) in das Regionalgefängnis Bern zurückverlegt, da er sich im Massnahmenvollzug in der Justizvollzugsanstalt Solothurn äusserst renitent verhalten hatte. A._ ersuchte um Erlass eines formellen Entscheids betreffend seine Verlegung. Die ASMV erliess am 30. November 2015 eine entsprechende Verfügung. Mit Beschwerde vom 11. November 2015 an die Polizei- und Militärdirektion des Kantons Bern beantragte A._ die Aufhebung der Verfügung vom 12. Oktober 2015. Er machte geltend, es sei rechtsstaatlich unhaltbar, ihn nach fast vierjähriger Haft zusätzlich für die Maximaldauer von weiteren 5 Jahren in eine Massnahmenanstalt einzuweisen. Zudem wäre das vorgesehene Massnahmenzentrum ungeeignet gewesen. Mit einer weiteren Beschwerde, datierend vom 1. Dezember 2015 beantragte A._ zudem, die Verfügung vom 30. Oktober 2015 sei aufzuheben und es sei seine Rückversetzung in Sicherheitshaft anzuordnen. Mit Entscheid vom 14. April 2016 wies die Polizei- und Militärdirektion die Beschwerde vom 11. November 2015 ab, soweit sie darauf eintrat, und trat auf die Beschwerde vom 1. Dezember 2015 nicht ein. Mit Beschwerde vom 12. Mai 2016 ans Obergericht des Kantons Bern beantragte A._, der Entscheid der Polizei- und Militärdirektion sei aufzuheben und es sei festzustellen, dass die Einweisungsverfügung vom 12. Oktober 2015 gegenstandslos sei und er sich formell nicht mehr im Massnahmenvollzug befinde. Zudem sei festzustellen, dass sein Aufenthalt im Regionalgefängnis Bern sich nicht auf Art. 30 Abs. 2 bzw. Art. 10 lit. g SMVG abstütze. Mit einer weiteren Eingabe desselben Datums beantragte A._, er sei umgehend aus der Haft zu entlassen und es sei ihm eine angemessene Entschädigung für die zu Unrecht ausgestandene Haft auszurichten. Mit Verfügung vom 13. Mai 2016 beschränkte das Obergericht das Verfahren vorläufig auf die Frage, ob auf das Haftentlassungsgesuch einzutreten sei. Mit Beschluss vom 26. Mai 2016 trat es darauf nicht ein. B. Mit Beschwerde in Strafsachen vom 14. Juni 2016 ans Bundesgericht beantragt A._, der Beschluss des Obergerichts sei aufzuheben und dieses sei anzuweisen, das Haftentlassungsgesuch an die Hand zu nehmen. Das Obergericht hat auf eine Vernehmlassung verzichtet. Die Generalstaatsanwaltschaft des Kantons Bern hat sich nicht vernehmen lassen