Sachverhalt:
A. X._ erstattete am 26. August 2010 Strafanzeige gegen seine von ihm getrennt lebende Ehefrau Y._ wegen falscher Anschuldigung im Sinne von <ref-law>. Gleichzeitig machte er Zivilforderungen geltend. Mit Entscheid vom 18. Oktober 2010 stellte das damals für die Untersuchung zuständige Amtsstatthalteramt Luzern das Strafverfahren gegen Y._ ein und trat auf die Zivilforderungen von X._ nicht ein.
Gegen den Einstellungsentscheid reichte X._ am 15. November 2010 Rekurs ein. Er beantragte die Überweisung der Strafsache an das zuständige Gericht und ersuchte zudem um Gewährung unentgeltlicher Rechtspflege. Mit Entscheid vom 25. März 2011 trat das Obergericht des Kantons Luzern auf den Rekurs nicht ein. Eine dagegen erhobene Beschwerde hiess das Bundesgericht mit Urteil vom 15. Juli 2011 gut und wies die Sache zur neuen Beurteilung an die Vorinstanz zurück (Verfahren 1B_236/2011). Das erneut mit der Sache befasste Obergericht trat mit Beschluss vom 30. November 2011 auf das Rechtsmittel ein, wies es jedoch in der Sache ab.
B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 26. Januar 2012 beantragt X._, der Beschluss des Obergerichts vom 30. November 2011 sei aufzuheben, die Strafanzeige wegen falscher Beschuldigung sei gutzuheissen und die Vorinstanz sei anzuweisen, im Sinne der Erwägungen über die Strafe und die adhäsionsweise geltend gemachten Zivilforderungen zu entscheiden.
Das Obergericht beantragt, auf die Beschwerde nicht einzutreten und eventualiter, sie abzuweisen. Die Oberstaatsanwaltschaft und die Beschwerdegegnerin haben auf eine Stellungnahme verzichtet. In seiner Replik hält der Beschwerdeführer an seinen Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Der angefochtene Entscheid betrifft die Einstellung einer Strafuntersuchung. Dagegen ist die Beschwerde in Strafsachen nach <ref-law> gegeben. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass (vgl. Urteil 1B_236/2011 vom 15. Juli 2011 E. 1 f.). Auf die Beschwerde ist einzutreten.
1.2 Die Einstellungsverfügung datiert vom 18. Oktober 2010. Anwendbar war deshalb bis zum erwähnten bundesgerichtlichen Urteil vom 15. Juli 2011 das Gesetz des Kantons Luzern vom 3. Juni 1957 über die Strafprozessordnung (SRL 305) und nicht die Schweizerische Strafprozessordnung (StPO; SR 312.0). Mit dem bundesgerichtlichen Urteil wurde die Sache zur neuen Beurteilung an das Obergericht zurückgewiesen. <ref-law> sieht vor, dass neues Recht anwendbar ist, wenn ein Verfahren von der Rechtsmittelinstanz oder vom Bundesgericht zur neuen Beurteilung zurückgewiesen wird. Dies bedeutet jedoch nicht, dass die Rechtmässigkeit der Einstellung ab diesem Zeitpunkt neu nach der StPO (siehe <ref-law>) zu beurteilen wäre. Nach der StPO hatte sich wohl das nach der Rückweisung durchgeführte Beschwerdeverfahren vor dem Obergericht zu richten (vgl. <ref-law>); auch wäre beispielsweise ein nach der Rückweisung eingereichtes Ausstandsgesuch gegenüber den mitwirkenden Oberrichtern nach den Bestimmungen der StPO zu beurteilen gewesen (vgl. <ref-law>). Aus Gründen der Verfahrenskohärenz beurteilte und beurteilt sich dagegen die Zulässigkeit der Verfahrenseinstellung weiterhin nach altem Recht. Diese Lösung steht in Einklang mit dem zentralen intertemporalrechtlichen Grundsatz von <ref-law>, wonach Verfahrenshandlungen, die vor Inkrafttreten dieses Gesetzes angeordnet oder durchgeführt worden sind, ihre Gültigkeit behalten (Urteil 1B_275/2011 vom 2. September 2011 E. 1.2 mit Hinweisen).
Anzufügen ist, dass im vorliegenden Fall die richtige Bestimmung des anwendbaren Prozessrechts nicht von entscheidender Bedeutung ist, da der Grundsatz "in dubio pro duriore", auf welchen sich sowohl die Vorinstanz wie auch der Beschwerdeführer stützen, schon vor Inkrafttreten der Schweizerischen Strafprozessordnung (auch) bundesrechtlicher Natur war.
2. 2.1 Der Beschwerdeführer wurde mit Strafverfügung vom 14. Dezember 2009 der mehrfachen Tätlichkeiten, der mehrfachen Drohung, des geringfügigen Diebstahls, des Diebstahls, der mehrfachen Sachbeschädigung, des mehrfachen Hausfriedensbruchs, des Ungehorsams gegen amtliche Verfügung und der Freiheitsberaubung schuldig gesprochen und zu einer bedingten Geldstrafe von 120 Tagessätzen zu je Fr. 100.-- und einer Busse von Fr. 600.-- verurteilt. Mit separatem Entscheid gleichen Datums wurde eine Teileinstellung betreffend mehrfache sexuelle Nötigung verfügt. Das Amtsstatthalteramt Luzern führte zur Begründung aus, die Beschwerdegegnerin habe ausgesagt, ihr Ehemann habe ihr Schmuck gegeben und als Gegenleistung Sex verlangt. Sie habe weiter ausgesagt, ihr Ehemann habe sie, wenn auch nicht physisch, so doch psychisch, zu sexuellen Handlungen genötigt, indem er ihr mit der Auflösung des Trennungsvertrags und der Sorgerechtsvereinbarung sowie mit Strafanzeigen gedroht habe; zudem sei er ohne Sex wütend geworden und habe angefangen herumzuschreien oder habe so getan, als wolle er sie schlagen. Es sei indessen fraglich, ob die Beschwerdegegnerin dadurch unter solchen psychischen Druck gesetzt wurde, dass sie deshalb auf ihre sexuelle Selbstbestimmung verzichtet habe. Sie habe sich ab Mitte März 2009 wieder freiwillig mit dem Angeschuldigten getroffen. Sie sei deshalb nicht in einer derart auswegslosen Situation gewesen, in welcher es ihr nicht zumutbar gewesen wäre, sich dem Vorhaben des Beschwerdeführers zu widersetzen. Zudem sei sie damals bezüglich der Trennungs- und Sorgerechtsvereinbarung bereits anwaltlich vertreten und von der Opferberatungsstelle betreut gewesen. In Bezug auf den Vorwurf der sexuellen Nötigung liege nur die Aussage des Opfers vor. Das Verfahren sei deshalb mangels rechtsgenüglichen Beweises in Bezug auf diesen Tatbestand einzustellen.
Am 26. August 2010 erstattete der Beschwerdeführer gegen die Beschwerdegegnerin Anzeige wegen falscher Anschuldigung. Am 18. Oktober 2010 stellte das Amtsstatthalteramt Luzern indessen die Strafuntersuchung ein. Es führte aus, der Beschwerdeführer könne sich nicht darauf berufen, nicht schuldig im Sinne von <ref-law> zu sein. Er sei wegen der von der Beschwerdegegnerin geschilderten Vorfälle rechtskräftig bestraft worden. Dass die Tätlichkeiten und Drohungen als nicht so intensiv qualifiziert worden seien, dass von einer sexuellen Nötigung ausgegangen werden musste, sei das Ergebnis der rechtlichen Beurteilung des Sachverhalts durch das Amtsstatthalteramt. Eine Beschuldigung wider besseres Wissen durch die Beschwerdegegnerin liege folglich nicht vor bzw. könne nicht nachgewiesen werden.
Das Obergericht bestätigte im angefochtenen Entscheid die Ausführungen des Amtsstatthalteramts. Ergänzend hielt es fest, die Beschwerdegegnerin habe konkrete Ausführungen zu den einzelnen Tathandlungen gemacht und es sei nachvollziehbar, dass die zeitliche Einordnung jedes einzelnen Vorfalls über einen Zeitraum von mehreren Jahren schwierig gewesen sei. Dass das Strafverfahren gegen den Beschwerdeführer teilweise eingestellt worden sei, bedeute nicht, dass die Strafanzeige selbst wider besseres Wissen erhoben worden sei. Eine Verurteilung der Beschwerdegegnerin wegen falscher Anschuldigung wäre insgesamt höchst unwahrscheinlich.
2.2 Der Beschwerdeführer kritisiert den vorinstanzlichen Entscheid und rügt sinngemäss eine Verletzung des strafprozessualen Grundsatzes "in dubio pro duriore". Er bringt vor, dass seine Unschuld in Bezug auf den Tatbestand der sexuellen Nötigung als erwiesen erachtet werden müsse, auch wenn das Verfahren lediglich eingestellt worden sei und er keine Gelegenheit gehabt habe, seine Unschuld zu beweisen. Die Beschwerdegegnerin habe sehr detailliert ausgeführt, was er alles gemacht habe. Dass sich dies nicht so zugetragen habe, wisse sie selber. Weil seine eigene Unschuld anerkannt werden müsse, sei das sichere Wissen über die unwahre Behauptung bewiesen. Die Drohungen und Tätlichkeiten, wegen derer er verurteilt worden sei, stünden mit dem Tatbestand der sexuellen Nötigung in keinem Zusammenhang. Man könne nicht davon ausgehen, dass ein Laie diese Delikte miteinander verwechseln könne. Hätte die Beschwerdegegnerin nicht die Absicht gehabt, eine Strafverfolgung gegen ihn herbeizuführen, wären ihre Ausführungen nie so detailliert gewesen. Diese erschienen auch deshalb als unglaubwürdig, weil sie nach langer Zeit noch ins kleinste Detail gegangen seien. Bedenklich seien sie weiter, weil die angeblichen sexuellen Nötigungen bereits vor der Geburt des gemeinsamen Kinds stattgefunden haben sollten und somit in keinem Zusammenhang mit der Trennungs- und Sorgerechtsvereinbarung stehen konnten. Es sei auch erstaunlich, dass sich die Beschuldigte nach so vielen Übergriffen nur noch an die letzten ausführlich habe erinnern können, könnte man doch annehmen, dass sich ein Opfer an die Situation "gewöhne" und deshalb vielmehr die erste sexuelle Nötigung am überraschendsten und schlimmsten sei.
2.3 Bei der Frage, ob ein Strafverfahren über eine (definitive) Verfahrenseinstellung durch die Strafverfolgungsbehörde erledigt werden kann, gilt im schweizerischen Strafprozessrecht der Grundsatz "in dubio pro duriore". Danach ist das Strafverfahren grundsätzlich fortzusetzen, wenn sich die Umstände, die für bzw. gegen eine Verurteilung sprechen, ungefähr die Waage halten. Der Strafverfolgungsbehörde, welche über die Einstellung entscheidet, kommt bei ihrem Entscheid ein erheblicher Ermessensspielraum zu. Sie hat dabei die auf dem Spiel stehenden Interessen zu berücksichtigen und insbesondere bei schweren Delikten eher von einer Einstellung abzusehen (zur Publ. bestimmtes Urteil 1B_687/2011, 1B_689/2011 vom 27. März 2012 E. 4.1 f.).
2.4 Gemäss <ref-law> wird mit Freiheitsstrafe oder Geldstrafe bestraft, wer einen Nichtschuldigen wider besseres Wissen bei der Behörde eines Verbrechens oder Vergehens beschuldigt, in der Absicht, eine Strafverfolgung gegen ihn herbeizuführen. Der Tatbestand der falschen Anschuldigung schützt in erster Linie die Zuverlässigkeit der Rechtspflege. Die Tathandlung führt zu einem unnützen Einsatz öffentlicher Mittel. Daneben handelt es sich bei der falschen Anschuldigung aber auch um ein Delikt gegen die Person. Geschützt werden danach die Persönlichkeitsrechte zu Unrecht Angeschuldigter mit Bezug auf deren Ehre, Freiheit, Privatsphäre, Vermögen usw. (<ref-ruling> E. 2.1 S. 175 f. mit Hinweis).
2.5 Dem Beschwerdeführer ist insoweit zuzustimmen, als die Einstellung des Verfahrens wegen sexueller Nötigung die rechtliche Wirkung eines Freispruchs hat, auch wenn sie mangels Beweisen erfolgt (<ref-ruling> E. 2.1 S. 165 mit Hinweisen; Urteil 1B_3/2011 vom 20. April 2011 E. 2.3). Dies ist jedoch vorliegend nicht allein entscheidend. Falsche Anschuldigung im Sinne von <ref-law> setzt eine Beschuldigung wider besseres Wissen voraus. Es müsste also Hinweise darauf geben, dass die Beschwerdegegnerin bewusst falsche Behauptungen gemacht hat. In diesem Zusammenhang erscheint der Hinweis der Vorinstanzen wesentlich, dass immerhin eine Verurteilung wegen mehrfachen Tätlichkeiten und mehrfacher Drohung erfolgte und dass im Zeitpunkt der Aussagen der Beschwerdegegnerin das Strafverfahren in Bezug auf den Tatbestand der sexuellen Nötigung noch nicht eingestellt worden war (vgl. dazu <ref-ruling> E. 2.2 S. 177, wonach sich aus dem Umstand, dass ein Strafverfahren eingestellt wird, nicht ableiten lässt, die Strafanzeige sei wider besseres Wissen gegen einen Nichtschuldigen erhoben worden). Dass die Beschwerdegegnerin davon ausging, das Verhalten des Beschwerdeführers habe ebenfalls den Tatbestand der sexuellen Nötigung erfüllt, ist nicht massgeblich. Das Amtsstatthalteramt hat diesbezüglich zu Recht ausgeführt, es handle sich dabei um eine Frage der rechtlichen Würdigung des Sachverhalts. Eine falsche Anschuldigung käme vielmehr nur in Betracht, wenn die Beschwerdegegnerin bewusst unwahre tatsächliche Behauptungen aufgestellt hätte, um den Vorwurf der sexuellen Nötigung zu begründen. Gemäss der Einstellungsverfügung und dem angefochtenen Entscheid gibt es dafür keine Anzeichen. Was der Beschwerdeführer dagegen vorbringt, ist offensichtlich nicht geeignet, diese Einschätzung in Frage zu stellen. Dass die Ausführungen der Beschwerdegegnerin detailliert gewesen sind, dass sie sich aber an lange zurück liegende Ereignisse nicht gleich gut hat erinnern können, ist leicht nachvollziehbar. Nicht nachvollziehbar ist dagegen die Behauptung des Beschwerdeführers, es sei bedenklich, dass die angeblichen sexuellen Nötigungen bereits vor der Geburt des gemeinsamen Kinds stattgefunden haben sollten und somit in keinem Zusammenhang mit der Trennungs- und Sorgerechtsvereinbarung stehen konnten. Aus den Akten wie auch aus den Entscheiden der Vorinstanzen geht klar hervor, dass die Beschwerdegegnerin verschiedene Arten von Druckversuchen beschrieb und dass diese nur teilweise im Zusammenhang mit der Trennungs- und Sorgerechtsvereinbarung standen.
2.6 Die Einschätzung der Vorinstanz, eine Verurteilung der Beschwerdegegnerin wegen falscher Anschuldigung sei als höchst unwahrscheinlich zu betrachten, ist nicht zu beanstanden. Die definitive Einstellung des Verfahrens verstösst somit nicht gegen den strafprozessualen Grundsatz "in dubio pro duriore" und ist insofern nicht bundesrechtswidrig. Die Rüge des Beschwerdeführers ist unbegründet.
3. Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist.
Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Prozessführung. Gemäss <ref-law> befreit das Bundesgericht eine Partei, die nicht über die erforderlichen Mittel verfügt, auf Antrag von der Bezahlung der Gerichtskosten, sofern ihr Rechtsbegehren nicht aussichtslos erscheint. Nach der bundesgerichtlichen Rechtsprechung sind Begehren als aussichtslos anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Massgebend ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschliessen würde. Eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.3.1 S. 135 f.; <ref-ruling> E. 5 S. 616; je mit Hinweisen). Ob eine Beschwerde aussichtsreich ist, erschliesst sich aus den Begehren und ihrer Begründung durch den Beschwerdeführer (Urteil 6B_588/2007 vom 11. April 2008 E. 6.2, in: Pra 2008 Nr. 123 S. 766). Wie sich aus den vorangehenden Erwägungen ergibt, sind vorliegend die Begehren offensichtlich unbegründet. Infolge Aussichtslosigkeit des Rechtsmittels entfällt deshalb der Anspruch auf unentgeltliche Rechtspflege nach <ref-law>. Der Beschwerdeführer trägt somit die Gerichtskosten (<ref-law>). Er hat zudem keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Es wird keine Parteientschädigung zugesprochen.
5. Dieses Urteil wird den Parteien, der Oberstaatsanwaltschaft und dem Obergericht des Kantons Luzern, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 4. April 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold