Sachverhalt: A. Die Bausektion der Stadt Zürich erteilte am 21. Juni 2011 der Orange Communications SA die Bewilligung zum Bau einer Mobilfunkantennenanlage auf dem Grundstück Kat.-Nr. OB2989 an der Frohburgstrasse 174 in Zürich. Dagegen erhob Rechtsanwalt U._ im Namen der X._ GmbH, der Stockwerkeigentümergemeinschaft Y._ sowie Z._, T._, W._ und V._ Rekurs ans Baurekursgericht des Kantons Zürich. Dieses trat mit Entscheid vom 25. November 2011 auf das Rechtsmittel nicht ein. Zur Begründung führte es aus, der Rechtsvertreter habe seine Befugnis zur Vertretung der Stockwerkeigentümergemeinschaft Y._ nicht nachgewiesen und bezüglich der übrigen Rekurrenten sei die Legitimation nicht hinreichend dargelegt worden. Die Verfahrenskosten auferlegte das Baurekursgericht den Rekurrenten und Rechtsanwalt U._, wobei es die Stockwerkeigentümergemeinschaft davon ausnahm. In der Folge gelangten die X._ GmbH, die Stockwerkeigentümergemeinschaft Y._, Z._, T._, W._, V._ und U._ ans Verwaltungsgericht des Kantons Zürich. Dieses schrieb mit Urteil vom 25. April 2012 die Beschwerde von T._ wegen Rückzugs des Rechtsmittels ab, trat auf die Beschwerde der Stockwerkeigentümergemeinschaft Y._ nicht ein und wies jene der übrigen Beschwerdeführer ab. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiärer Verfassungsbeschwerde ans Bundesgericht beantragen die X._ GmbH, die Stockwerkeigentümergemeinschaft Y._, Z._, W._, V._ und U._ im Wesentlichen, das Urteil des Verwaltungsgerichts sei - abgesehen von der Abschreibung der Beschwerde von T._ - aufzuheben. Ebenfalls aufzuheben sei der Entscheid des Baurekursgerichts und dieses sei anzuweisen, die Sache materiell zu behandeln. Das Verwaltungsgericht beantragt in seiner Vernehmlassung, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Baurekursgericht und die Beschwerdegegnerin schliessen auf Abweisung der Beschwerde. Die Bausektion der Stadt Zürich hat auf eine Vernehmlassung verzichtet, ebenso die Beschwerdeführer auf eine Replik.