Sachverhalt:
A. Am 11. Juli 2006 genehmigte der Regierungsrat des Kantons Solothurn auf Antrag der Einwohnergemeinde Breitenbach den Teilzonenplan "Central" mit Zonenvorschriften sowie die Gestaltungspläne mit Sonderbauvorschriften "Central" und "Central Süd". Die Südgrenze des Gestaltungsplanperimeters "Central" und die Nordgrenze des Gestaltungsplanperimeters "Central Süd" überlagern sich entlang der gemeinsamen Parzellengrenze.
Anfangs 2007 reichte die Y._ AG ein Baugesuch für die Überbauung "Central" ein. Die im Auflageverfahren erhobenen Einsprachen wurden zurückgezogen. Die Baukommission Breitenbach genehmigte das Baugesuch mit Entscheid vom 30. Juli 2007. In der Folge wurde mit dem Bau begonnen. Im August 2007 reichte die X._ AG ein Baugesuch für die Überbauung "Central Süd" ein. Die Y._ AG erhob dagegen Einsprache. Zwischen den beiden Bauherrschaften fanden erfolglose Verhandlungen über eine Grenzbereinigung entlang der Parzellen Nr. 2232 (Gestaltungsplanperimeter "Central Süd") und 1864 (Gestaltungsplanperimeter "Central") sowie über den Abschluss eines Dienstbarkeitsvertrags für ein Geh- und Fahrwegrecht durch die Autoeinstellhalle der Überbauung "Central" zur Laufenstrasse hin statt.
Am 24. Januar 2008 ordnete die Baukommission an, die beiden Bauherrschaften hätten eine Grunddienstbarkeit für die Durchfahrt durch das erste Untergeschoss der Einstellhalle der Überbauung "Central" zu vereinbaren. Die Y._ AG wurde verpflichtet, die Wandaussparung zur Tiefgarage auf Parzelle Nr. 2232 nicht auszubetonieren. Gegen diese Verfügung erhoben beide Bauherrschaften Beschwerde beim Bau- und Justizdepartement des Kantons Solothurn. Dieses untersagte vorläufig der Y._ AG die Inanspruchnahme der Parzelle Nr. 2232 mittels Baustopp. Mit Verfügung vom 6. November 2008 entschied das Bau- und Justizdepartement unter anderem, dass die Baubewilligung für die Überbauung "Central" rechtmässig sei. Zur Begründung führte es aus, die X._ AG sei im Baubewilligungsverfahren bezüglich der Überbauung "Central" nicht Partei gewesen. Ihre Einsprache sei verspätet, auch wenn das Bauvorhaben geringfügig abgeändert worden sei. Eine erneute Publikation sei nicht notwendig gewesen. Der Situationsplan der Baueingabe habe zwar einen in den Gestaltungsplänen nicht vorgesehenen Abtausch von 1 m2 Land entlang der Grenze vorgesehen. Nachträglich habe die Baukommission aber die Rückversetzung der Südfassade um 8 cm bewilligt, um sicherzustellen, dass die Y._ AG nicht auf fremdem Boden baue. Damit sei die Grenzbereinigung hinfällig geworden. Diese Änderung der Baubewilligung ohne erneute Publikation sei zulässig gewesen. Ein Gutachten wie auch die nachträglich eingereichten Pläne hätten gezeigt, dass keine Verletzung der Grenze bestehe.
Eine gegen diesen Entscheid des Bau- und Justizdepartements gerichtete Beschwerde der X._ AG wurde vom Verwaltungsgericht des Kantons Solothurn mit Urteil vom 8. Juni 2009 abgewiesen.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 10. Juli 2009 beantragt die X._ AG im Wesentlichen, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei die Nichtigkeit der an die Y._ AG erteilten Baubewilligung festzustellen, eventualiter sei die Baubewilligung zu widerrufen. Zudem sei die Bauverwaltung Breitenbach anzuweisen, der Beschwerdeführerin die Baubewilligung für die Überbauung "Central Süd" zu erteilen, unter gleichzeitiger Regelung der Mitbenutzung der Erschliessung gemäss § 104 des Planungs- und Baugesetzes des Kantons Solothurn vom 3. Dezember 1978 (BGS 711.1; im Folgenden: PBG) zu Lasten der Beschwerdegegnerin.
Das Verwaltungsgericht des Kantons Solothurn und die Beschwerdegegnerin beantragen in ihrer Vernehmlassung die Abweisung der Beschwerde. Das Bau- und Justizdepartement des Kantons Solothurn beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Baukommission der Einwohnergemeinde Breitenbach liess sich nicht vernehmen. Die Beschwerdeführerin hält in einer unaufgefordert eingereichten Stellungnahme im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Dem angefochtenen Entscheid liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zu Grunde. Nach Art. 34 Abs. 1 RPG (SR 700) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält keinen Ausschlussgrund (<ref-law>). Angefochten ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Die Beschwerdeführerin hat am vorinstanzlichen Verfahren teilgenommen, ist durch den angefochtenen Entscheid besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Unter dem Vorbehalt der nachfolgenden Erwägungen ist auf die Beschwerde einzutreten.
1.2 Gemäss <ref-law> sind neue Begehren unzulässig. Die Beschwerdeführerin beantragt in ihrer Beschwerde an das Bundesgericht, die Bauverwaltung Breitenbach sei anzuweisen, der Beschwerdeführerin die Baubewilligung für die Überbauung "Central Süd" zu erteilen, unter gleichzeitiger Regelung der Mitbenutzung der Erschliessung gemäss § 104 PBG zu Lasten der Beschwerdegegnerin. Dieser Antrag wurde im vorinstanzlichen Verfahren nicht gestellt. Er ist neu, weshalb darauf nicht einzutreten ist.
1.3 Die Feststellung und Würdigung der tatsächlichen Verhältnisse überprüft das Bundesgericht im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten nach Massgabe der Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG. Voraussetzung dazu ist, dass rechtsgenügend begründete Sachverhaltsrügen im Sinne von <ref-law> erhoben werden.
Die Beschwerdeführerin macht eigene Ausführungen zum Sachverhalt und bestreitet insbesondere die Feststellung der Vorinstanz, es hätten erst nach der Baueinsprache durch die Beschwerdegegnerin erfolglose Verhandlungen stattgefunden. Sie legt indessen nicht dar, inwiefern die Behebung des behaupteten Mangels in der Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend sein könnte (<ref-law>). Auf das Vorbringen ist deshalb nicht einzutreten.
2. 2.1 Die Beschwerdeführerin macht geltend, die Baubewilligung vom 30. Juli 2007 sei nichtig. Sie verletze in schwerwiegender Weise die Eigentumsgarantie (<ref-law>). Nach § 130 PBG hätten die Behörden dafür zu sorgen, dass Bauten und bauliche Anlagen dem Planungs- und Baugesetz, den gestützt darauf erlassenen Bauvorschriften und Nutzungsplänen und den übrigen öffentlich-rechtlichen Vorschriften des Bundes, des Kantons und der Gemeinde entsprächen. Das Baugesuch habe gemäss § 5 Abs. 1 lit. a der Kantonalen Bauverordnung vom 3. Juli 1978 (BGS 711.61; im Folgenden: KBV) genaue Angaben über die Eigentumsverhältnisse (Eigentumsnachweis, Baurechtsvertrag oder schriftliche Zustimmung des Grundeigentümers) zu enthalten. Die Behörden seien verpflichtet, im Rahmen ihrer Amtspflicht von Amtes wegen tätig zu werden, die zur Abklärung des Sachverhalts notwendigen Erhebungen selbständig vorzunehmen und das Recht von Amtes wegen anzuwenden (§ 14 des Gesetzes des Kantons Solothurn vom 15. November 1970 über den Rechtsschutz in Verwaltungssachen [Verwaltungsrechtspflegegesetz; BGS 124.11]). Diese Bestimmungen und damit auch Art. 22 RPG seien verletzt worden, als die Baubewilligungsbehörde der Beschwerdegegnerin erlaubt habe, auf fremdem Boden zu bauen. In diesem Zusammenhang beruft sich die Beschwerdeführerin auch auf § 12 Abs. 3 KBV, der die Abweichung von genehmigten Plänen regelt. Von genehmigten Plänen könne im Falle von deren Nichtigkeit nicht gesprochen werden. Schliesslich macht sie geltend, die Baubewilligung hätte ihr als direkt Betroffener förmlich eröffnet werden müssen, was nicht geschehen sei.
2.2 Fehlerhafte Verwaltungsakte sind in der Regel nicht nichtig, sondern nur anfechtbar, und sie werden durch Nichtanfechtung rechtsgültig. Nichtigkeit, d.h. absolute Unwirksamkeit einer Verfügung, wird nur angenommen, wenn der ihr anhaftende Mangel besonders schwer wiegt, wenn er offensichtlich oder zumindest leicht erkennbar ist und wenn zudem die Rechtssicherheit durch die Annahme der Nichtigkeit nicht ernsthaft gefährdet wird. Inhaltliche Mängel haben nur in seltenen Ausnahmefällen die Nichtigkeit einer Verfügung zur Folge. Als Nichtigkeitsgründe fallen hauptsächlich funktionelle und sachliche Unzuständigkeit einer Behörde sowie schwer wiegende Verfahrensfehler in Betracht (<ref-ruling> E. 3 S. 26 ff., insbesondere E. 3.1 S. 27 mit Hinweisen).
2.3 Das Bau- und Justizdepartement führte zur unterbliebenen Mitteilung aus, Einsprachen gegen ein Bauvorhaben seien nach § 8 Abs. 1 KBV während der öffentlichen Auflage des Baugesuchs zu erheben. Dies habe die Beschwerdeführerin nicht getan. Gegen das Baugesuch sei zwar innerhalb der Auflagefrist eine Einsprache eingegangen, diese sei jedoch wieder zurückgezogen worden. Die Baukommission habe deshalb im Rahmen der Erteilung der Baubewilligung am 30. Juli 2007 nicht über Einsprachen zu entscheiden gehabt. Auch sei sie nicht verpflichtet gewesen, die Baubewilligung der Beschwerdeführerin zuzustellen. Diese sei im Baubewilligungsverfahren nicht Partei gewesen. Gestützt unter anderem auf diese Erwägung des Bau- und Justizdepartements ging auch das Verwaltungsgericht davon aus, die Baubewilligung sei in formelle Rechtskraft erwachsen.
Die Beschwerdeführerin setzt sich mit diesen Erwägungen nicht in rechtsgenügender Weise auseinander (<ref-law>). Auf ihre Rüge, die Mitteilung der Baubewilligung sei in rechtswidriger Weise unterblieben, ist deshalb nicht einzutreten.
2.4 Wie bereits aus dem Entscheid des Bau- und Justizdepartements hervorgeht, bildete der Flächenabtausch an der gemeinsamen Parzellengrenze eine Auflage der Baubewilligung vom 30. Juli 2007. Nach diesem Entscheid handelt es sich um einen Abtausch von je 1 m2. Das Bauen auf dem Boden der Beschwerdeführerin wurde der Beschwerdegegnerin also nur insoweit erlaubt, als diese Frage zwischen den Parteien noch geregelt werden würde. Es ist nicht ersichtlich, dass damit die Eigentumsgarantie und die weiteren von der Beschwerdeführerin angeführten Rechtsnormen verletzt worden wären, sodass die Baubewilligung an einem Nichtigkeitsgrund litte. Daran ändert nach dem Gesagten auch der von der Beschwerdeführerin unter dem Titel von Treu und Glauben vorgebrachte Hinweis nichts, die Beschwerdegegnerin habe im Zeitpunkt der Erteilung der Baubewilligung gewusst, dass sie nicht Eigentümerin der ganzen zu überbauenden Fläche gewesen sei. Schliesslich ist für die Frage der Gültigkeit der Baubewilligung auch nicht von Bedeutung, dass die Beschwerdeführerin später mehrfach einen Baustopp verlangt hatte. Durfte die Vorinstanz somit davon ausgehen, die Baubewilligung vom 30. Juli 2007 sei nicht nichtig gewesen, so erweist sich die diesbezügliche Rüge der Beschwerdeführerin als unbegründet.
3. 3.1 Die Beschwerdeführerin kritisiert die Ausführungen des Verwaltungsgerichts zur Möglichkeit des nachträglichen Widerrufs der Baubewilligung. Eine umfassende Interessenabwägung habe nicht stattgefunden. Die Beschwerdeführerin wiederholt, das Baugesuch beinhalte die Überbauung fremden Eigentums und die Baugesuchstellerin habe dies gewusst, weshalb sie sich nicht auf den Vertrauensschutz berufen könne.
3.2 Sinngemäss macht die Beschwerdeführerin damit eine willkürliche Auslegung von § 22 Verwaltungsrechtspflegegesetz geltend. Gemäss dieser Bestimmung können Verfügungen und Entscheide durch die zuständige Behörde oder die Aufsichtsbehörde abgeändert oder widerrufen werden, falls sich die Verhältnisse geändert haben oder, sofern Rückkommensgründe bestehen, überwiegende Interessen dies erfordern. Die Vorinstanz erwog dazu, der Situationsplan der Baueingabe habe einen in den Gestaltungsplänen nicht vorgesehenen flächendeckenden Abtausch von 1 m2 Land enthalten. Mit dem Bau des Zentrums sei begonnen worden und die rechtskräftige Baubewilligung habe gestaltende Wirkung. Dem Vertrauensschutz sei insgesamt der Vorrang einzuräumen.
Die Argumentation der Beschwerdeführerin, welche im Wesentlichen ihre Vorbringen zur Frage der Nichtigkeit wiederholt, vermag auch hier nicht zu überzeugen (vgl. E. 2.4 hiervor). Die Vorinstanz ist nicht in Willkür verfallen, wenn sie die Voraussetzungen der Kann-Bestimmung von § 22 Verwaltungsrechtspflegegesetz vorliegend als nicht erfüllt ansah.
4. 4.1 Die Beschwerdeführerin bringt weiter vor, die Genehmigung der nachträglichen Änderung der Baupläne sei zu Unrecht erfolgt. Die Rückversetzung der Fassade um 8 cm stehe im Widerspruch zum Gestaltungsplan "Central", welcher zwingend eine Grenzkorrektur vorsehe.
4.2 Die Beschwerdeführerin legt nicht dar, welche Bestimmungen des Gestaltungsplans eine Grenzkorrektur zwingend vorschreiben und damit die Rückversetzung der Fassade verbieten. Wie bereits ausgeführt, erwog die Vorinstanz im Zusammenhang mit der Frage des Widerrufs im Gegenteil, dass die Gestaltungspläne einen Abtausch von Landflächen nicht vorsehen würden. Auch darauf geht die Beschwerdeführerin nicht ein. Auf ihr Vorbringen ist nicht einzutreten (<ref-law>).
5. 5.1 Sinngemäss macht die Beschwerdeführerin sodann eine willkürliche Anwendung der Gestaltungspläne "Central" und "Central Süd" geltend. Diese würden ihr ein Wahlrecht hinsichtlich der Erschliessung der Überbauung "Central Süd" via die Überbauung "Central" hin zur Laufenstrasse einräumen. Aufgrund des Verhaltens der Beschwerdegegnerin und der Behörden habe sie mit dieser Erschliessungsvariante gerechnet und sei gestützt auf Art. 5 Abs. 3 und Art. 9 BV in ihrem Vertrauen zu schützen. Zudem bestehe eine Notwegsituation, denn die zuständige Baubewilligungsbehörde werde die Erschliessung über die Passwangstrasse nicht erlauben.
5.2 Das Verwaltungsgericht führt diesbezüglich aus, der Gestaltungsplan "Central Süd" schreibe die Erschliessung über die Passwangstrasse vor. Es verweist dabei auf die roten Pfeile, welche auf dem Plan eingezeichnet sind. Eine Durchfahrt zwischen den Parkgeschossen sei dagegen nicht dargestellt. Die Sonderbauvorschriften sprächen im Zweckartikel von der Festlegung der unterirdischen Parkierung mit der Möglichkeit der Anbindung benachbarter Autoeinstellhallen. Unter Ziff. 12 werde festgehalten, dass für den Baubereich des Gestaltungsplans "Central Süd" eine Option bestehe für die Erweiterung der Einstellhalle um maximal 24 Parkplätze. Die notwendigen privatrechtlichen Vereinbarungen müssten bis zur Baueingabe abgeschlossen und mit dem Baugesuch eingereicht werden. Diese Wendung enthalte keine öffentlich-rechtliche Verpflichtung für die Beschwerdegegnerin, so zu bauen, dass die Beschwerdeführerin das Parkgeschoss und die Ausfahrt der Beschwerdegegnerin nutzen dürfe. Ein derartiges Recht bestehe nur, wenn eine entsprechende Dienstbarkeit vorliege. Dies sei nicht der Fall. Die Anbindung an den Gestaltungsplan "Central" werde denn auch lediglich als Option erwähnt. Die Zufahrt in die neue Einstellhalle erfolge von Osten über die Passwangstrasse. Es sei unzulässig, die Parteien im Baubewilligungsverfahren zum Abschluss eines Dienstbarkeitsvertrags zur Realisierung dieser Option zu verhalten, zumal auch keine Notwegsituation bestehe.
5.3 Die Sonderbauvorschriften zum Gestaltungsplan "Central Süd" sehen unter dem Titel "Erschliessungskonzept" (Ziff. 11) im Wortlaut vor: "Die Fahrverkehrserschliessung ist nur über die im Gestaltungsplan bezeichneten Flächen zulässig. (...) Die Hauptzugänge erfolgen über die Passwangstrasse. Optional ist eine Erschliessung über das Central-Areal möglich." Auf dem Gestaltungsplan ist mit roten Pfeilen die Ein- und Ausfahrt von der Passwangstrasse zur Einstellhalle eingezeichnet. Das Verwaltungsgericht schloss hieraus, dass die Möglichkeit der Erschliessung über das "Central"-Areal nicht als Verpflichtung Dritter, eine Erschliessung über ihr Grundeigentum zu dulden, verstanden werden könne. Dabei legte es den Gestaltungsplan keineswegs willkürlich aus. Weshalb trotz der klaren Rechtslage von einer Vertrauensgrundlage hinsichtlich der von der Beschwerdeführerin angestrebten Erschliessungsvariante ausgegangen werden sollte, ist nicht ersichtlich. Die Vorinstanz hat kein Bundesrecht verletzt, wenn sie vor diesem Hintergrund ein Notwegrecht zugunsten der Beschwerdeführerin und überhaupt eine Pflicht der Beschwerdegegnerin zur Duldung der Inanspruchnahme ihres Grundeigentums verneinte.
6. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens hat die Beschwerdeführerin die Kosten des bundesgerichtlichen Verfahrens zu tragen (<ref-law>). Sie hat der obsiegenden, anwaltlich vertretenen Beschwerdegegnerin eine dem Aufwand entsprechende Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 300.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Einwohnergemeinde Breitenbach, dem Bau- und Justizdepartement sowie dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 3. Dezember 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold