Sachverhalt: A. Im Januar 2007 reichte die Swisscom Mobile AG (heute: Swisscom (Schweiz) AG; im Folgenden: Swisscom) ein Baugesuch ein, um ihre bestehende Mobilfunkanlage auf dem 14-geschossigen Hochhaus Grossmatt 1 in Kappel mit UMTS zu erweitern. Gleichzeitig stellte auch die Kantonspolizei Solothurn ein Gesuch um Erweiterung der bestehenden Kommunikationsanlage mit Polycom- und Richtfunkantennen; dieses Gesuch wurde jedoch am 5. Oktober 2007 zurückgezogen. Auf dem Dach des Hochhauses Grossmatt 1 befindet sich bereits eine Telepage-Anlage der Swissphone Wireless AG. Gegen das Bauvorhaben gingen zahlreiche Einsprachen ein, darunter auch der Einwohnergemeinde Kappel und der Eheleute X._. Am 20. August 2007 wies die Baukommission Kappel die Einsprachen ab und erteilte die Baubewilligung. B. Dagegen erhoben sowohl die Eheleute X._ als auch die Einwohnergemeinde Kappel Beschwerde an das Bau- und Justizdepartement des Kantons Solothurn. Dieses wies die Beschwerden am 19. Februar 2008 ab. C. Gegen den Departementsentscheid gelangten die Eheleute X._ mit Beschwerde an das Verwaltungsgericht des Kantons Solothurn. Auch die Einwohnergemeinde Kappel erhob Beschwerde, zog diese aber am 20. März 2008 zurück. Am 27. November 2008 wies das Verwaltungsgericht die Beschwerde ab. Es hielt im Dispositiv fest, dass die Anlage der Swisscom spätestens im Zeitpunkt der Inbetriebnahme in das Qualitätssicherungssystem der Swisscom zu integrieren sei. D. Am 26. Januar 2009 haben die Eheleute X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen die Aufhebung des angefochtenen Entscheids und der vorinstanzlichen Entscheide sowie die Abweisung des Baugesuchs. Ferner sei die Strahlenbelastung des bestehenden Telepage-Funkdiensts der Swissphone Wireless AG zu messen und diese Anlage sei an den Standort Gunzgen zu verschieben, an den bereits die KAPO Solothurn ihren Funkdienst im laufenden Verfahren verschoben hat. Eventuell sei die Streitsache an das Verwaltungsgericht zurückzuweisen. E. Die Baukommission Kappel, das Verwaltungsgericht sowie das Bau- und Justizdepartement schliessen auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Die Einwohnergemeinde Kappel hat auf eine Vernehmlassung verzichtet, verweist aber auf ihre seinerzeitige Beschwerde vom 29. Februar 2009. Die Swisscom verweist ihrerseits auf die Entscheide der Vorinstanzen, insbesondere des Verwaltungsgerichts. F. Das Bundesamt für Umwelt (BAFU) vertritt in seiner Vernehmlassung die Auffassung, das Verwaltungsgericht habe die Badezimmer im obersten Stock des Standortgebäudes zu Unrecht nicht als Orte mit empfindlicher Nutzung (OMEN) i.S.v. Art. 3 Abs. 3 lit. a der Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) anerkannt. Es seien zusätzliche Sachverhaltsabklärungen erforderlich, um festzustellen, ob der Anlagegrenzwert an diesen Orten eingehalten werde. Den Beteiligten wurde Gelegenheit gegeben, hierzu Stellung zu nehmen. G. Mit Verfügung vom 26. Februar 2009 wurde der Beschwerde die aufschiebende Wirkung in dem Sinne erteilt, dass die neuen Mobilfunkantennen während der Dauer des bundesgerichtlichen Verfahrens nicht in Betrieb genommen werden dürfen.