Sachverhalt:
A. Gegen X._ läuft ein Strafverfahren wegen Veruntreuung und weiterer Delikte. Am 8. April 2009 wurde ihm Rechtsanwältin Anne-Françoise Zuber als amtliche Verteidigerin beigegeben. Am 5. September 2011 ersuchte X._ um Wechsel der amtlichen Verteidigung, was die Oberstaatsanwaltschaft des Kantons Zürich mit Verfügung vom 14. September 2011 jedoch ablehnte. Eine von X._ gegen diese Verfügung eingereichte Beschwerde wies das Obergericht des Kantons Zürich mit Beschluss vom 7. Dezember 2011 ab.
B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 19. Dezember 2011 beantragt X._, der Beschluss des Obergerichts sei aufzuheben und sein Gesuch um Wechsel der amtlichen Verteidigung sei zu bewilligen.
Die Oberstaatsanwaltschaft und das Obergericht des Kantons Zürich haben auf eine Vernehmlassung verzichtet. Die amtliche Verteidigerin hat Stellung genommen, ohne einen Antrag in der Sache zu stellen. Sie weist insbesondere darauf hin, dass der Beschwerdeführer am 8. Februar 2008 in Abwesenheit vom Vorwurf der Erpressung freigesprochen worden sei und sie somit ohne seine Instruktionen erfolgreich auf Freispruch plädiert habe.

Erwägungen:
1. 1.1 Beim angefochtenen Entscheid handelt es sich um einen kantonal letztinstanzlichen Zwischenentscheid in Strafsachen (Art. 78, 80 und 93 BGG).
Genauer zu prüfen ist, ob die Sachurteilsvoraussetzungen von Art. 93 BGG erfüllt sind. Sofern sich diese nicht ohne Weiteres aus den Akten ergeben, obliegt es dem Beschwerdeführer darzulegen, inwiefern sie gegeben sind (<ref-ruling> E. 1 S. 356). Der Beschwerdeführer macht in dieser Hinsicht geltend, die Verweigerung der Auswechslung des amtlichen Verteidigers könne einen nicht wieder gutzumachenden Nachteil bewirken (Art. 93 Abs. 1 lit. a BGG).
1.2 Als oberste rechtsprechende Behörde des Bundes soll sich das Bundesgericht in der Regel nur einmal mit der gleichen Streitsache befassen müssen. Nach ständiger Praxis zu Art. 93 Abs. 1 lit. a BGG ist ein Vor- oder Zwischenentscheid daher nur ausnahmsweise anfechtbar, sofern ein konkreter rechtlicher Nachteil droht, der auch durch einen (für die rechtsuchende Partei günstigen) Endentscheid nachträglich nicht mehr behoben werden könnte. Der blosse Umstand, dass es sich beim aktuellen Offizialverteidiger nicht (oder nicht mehr) um den Wunsch- bzw. Vertrauensanwalt eines Beschuldigten handelt, schliesst eine wirksame und ausreichende Verteidigung nicht aus. Die Ablehnung eines Gesuchs des Beschuldigten um Auswechslung des amtlichen Verteidigers begründet daher grundsätzlich keinen nicht wieder gutzumachenden Rechtsnachteil im Sinne des Gesetzes. Anders kann der Fall liegen, wenn der amtliche Verteidiger seine Pflichten erheblich vernachlässigt, wenn die Strafjustizbehörden gegen den Willen des Beschuldigten und seines Offizialverteidigers dessen Abberufung anordnen, oder wenn sie dem Beschuldigten verweigern, sich (zusätzlich zur Offizialverteidigung) auch noch durch einen Privatverteidiger vertreten zu lassen (zum Ganzen: <ref-ruling> E. 1.2-1.4 S. 264 f.; Urteile 1B_197/2011 vom 14. Juli 2011 E. 1; 1B_357/2010 vom 7. Januar 2011 E. 1; je mit Hinweisen).
1.3 Der Beschwerdeführer macht geltend, er habe einen Verteidigerwechsel beantragt, weil er sich von seiner amtlichen Verteidigerin nicht vertreten, abgeholt und verstanden fühle. Er habe absolut kein Vertrauen in sie und ihre Strategievorschläge. Er habe sich sogar geweigert, an einer Einvernahme mit seiner amtlichen Verteidigerin teilzunehmen. Es sei sehr verletzend, dass sie sich mit ihm nur via eine Trennscheibe unterhalte, zumal es nicht um ein Gewaltdelikt gehe. Eine effektive Verteidigung sei aber auch aufgrund ihrer Eingabe vom 4. November 2011 nicht mehr gewährleistet. Diese lese sich wie eine pointierte Eingabe gegen den eigenen Klienten. Dem Mandanten werde in markigen Worten zum Vorwurf gemacht, dass er von seinem Recht zur Aussageverweigerung Gebrauch mache. Ferner werde ihm unterstellt, er suche den Fehler stets bei anderen. Es werde ihm mehrfach Zwängerei vorgeworfen. Es sei insgesamt deutlich spürbar, dass die amtliche Verteidigerin sehr in Rage sei, sich über den eigenen Klienten enerviert habe und ihn geradezu schlecht mache.
1.4 Die amtliche Verteidigerin ist weiterhin bereit, ihre Aufgabe wahrzunehmen. Dies hat sie sowohl in ihrer Vernehmlassung zuhanden des Bundesgerichts als auch im erwähnten Schreiben vom 4. November 2011 zum Ausdruck gebracht. Sie kritisiert zwar das Verhalten des Beschwerdeführers deutlich, tut dies jedoch in sachlicher Weise und mit dem Ziel darzulegen, dass aus objektiver Sicht kein Anlass für den beantragten Wechsel der Verteidigung bestehe. Es könne keine Rede davon sein, dass sie den Beschwerdeführer schlecht machen wolle oder dass sie in Rage sei.
Dass die Gespräche in einem Zimmer mit Trennscheibe stattgefunden haben, erklärt die amtliche Verteidigerin damit, dass der Beschwerdeführer zuvor mit einem Sprung aus dem Fenster einen Suizidversuch unternommen habe. Diesen Umstand hat die Vorinstanz zu Recht als nachvollziehbare Begründung erachtet. Er wird zudem vom Beschwerdeführer nicht bestritten.
Insgesamt kann nicht gesagt werden, dass die amtliche Verteidigerin ihre Pflichten erheblich vernachlässigt hat oder dass sonst eine wirksame Verteidigung nicht mehr möglich ist. Die Sachurteilsvoraussetzungen von Art. 93 Abs. 1 lit. a BGG sind deshalb nicht erfüllt.
2. Auf die Beschwerde ist nicht einzutreten.
Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege. Da die gesetzlichen Voraussetzungen erfüllt sind, kann dem Gesuch entsprochen werden (Art. 64 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen.
2.1 Es werden keine Gerichtskosten erhoben.
2.2 Rechtsanwalt Stephan Bernard wird zum unentgeltlichen Rechtsbeistand ernannt und für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse mit Fr. 1'000.-- entschädigt.
3. Dieses Urteil wird dem Beschwerdeführer, Rechtsanwältin Anne-Françoise Zuber, der Oberstaatsanwaltschaft und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 8. Februar 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold