Sachverhalt:
A.
A._ wurde am 19. Januar 2018 im Berufungsverfahren durch das Obergericht des Kantons Zürich wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz und weiterer Delikte zu einer Freiheitsstrafe von zehn Jahren verurteilt. Auf Beschwerde hin hob das Bundesgericht das Urteil des Obergerichts auf und wies die Sache zur neuen Beurteilung zurück (Urteil des Bundesgerichts 6B_403/2018 vom 14. Januar 2019).
Am 25. Januar 2019 verlangte A._ den Ausstand von Staatsanwalt Umberto Pajarola. Er berief sich darauf, dass Letzterer am 29. Januar 2018 aufgrund der Äusserungen seines amtlichen Verteidigers anlässlich der obergerichtlichen Hauptverhandlung eine Strafanzeige erstattet habe. Die Staatsanwaltschaft leitete das Gesuch dem Obergericht weiter, das mit Beschluss vom 14. Oktober 2019 darauf nicht eintrat. Zur Begründung führte es aus, der Ausstandsgrund sei zu spät geltend gemacht worden.
B.
Mit Beschwerde in Strafsachen ans Bundesgericht vom 18. November 2019 beantragt A._, der Beschluss des Obergerichts sei aufzuheben und es sei festzustellen, dass Staatsanwalt Pajarola befangen sei und in den Ausstand zu treten habe. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen.
Das Obergericht hat auf eine Stellungnahme verzichtet. Die Staatsanwaltschaft, vertreten durch den Beschwerdegegner, beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Der Beschwerdeführer hält in seiner Stellungnahme dazu an seinen Anträgen und Rechtsauffassungen fest.

Erwägungen:
1.
Beim angefochtenen Urteil handelt es sich um einen selbständig eröffneten Zwischenentscheid über ein Ausstandsbegehren in einer Strafsache (Art. 78 Abs. 1 und Art. 92 Abs. 1 BGG). Das Obergericht hat als letzte und einzige kantonale Instanz entschieden (Art. 80 BGG i.V.m. Art. 59 Abs. 1 StPO). Der Beschwerdeführer ist gemäss Art. 81 Abs. 1 lit. a und lit. b Ziff. 1 BGG zur Beschwerde befugt. Zu prüfen ist jedoch einzig, ob das Obergericht zu Recht einen Nichteintretensentscheid fällte (<ref-ruling> E. 1.2 S. 41). Soweit der Beschwerdeführer darüber hinausgehend verlangt, der Beschwerdegegner sei in den Ausstand zu versetzen, ist auf die Beschwerde nicht einzutreten.
2.
2.1. Der Beschwerdeführer bringt vor, er habe im Zeitraum zwischen dem obergerichtlichen Urteil vom 19. Januar 2018 und seiner dagegen gerichteten Beschwerde ans Bundesgericht erfahren, dass der Beschwerdegegner gegen seinen amtlichen Verteidiger eine Strafanzeige erstattet habe. Damals sei das kantonale Strafverfahren bereits abgeschlossen gewesen. Es sei nicht absehbar gewesen, dass der Beschwerdegegner in dem Strafverfahren weitere Verfahrenshandlungen vornehmen würde. Ein Ausstandsgesuch wäre damals klarerweise unzulässig gewesen. Hinzu komme, dass er in seiner Beschwerde ans Bundesgericht auf den Ausstandsgrund hingewiesen und verlangt habe, dass der Beschwerdegegner nicht im bundesgerichtlichen Verfahren mitwirken dürfe. Erst durch die Rückweisung der Sache ans Obergericht sei eine weitere Mitwirkung des Beschwerdegegners absehbar geworden und erst zu jenem Zeitpunkt habe es wieder ein (konkretes) kantonales Strafverfahren gegeben. Entsprechend habe er am 25. Januar 2019 unverzüglich ein Ausstandsgesuch eingereicht. Im Übrigen seien Ausstandsgründe ohnehin von Amtes wegen zu berücksichtigen.
2.2. Gemäss Art. 56 lit. f StPO tritt eine in einer Strafbehörde tätige Person in den Ausstand, wenn sie aus anderen Gründen, insbesondere wegen Freundschaft oder Feindschaft mit einer Partei oder deren Rechtsbeistand, befangen sein könnte. Gemäss Art. 58 Abs. 1 StPO hat die Partei, die den Ausstand einer in einer Strafbehörde tätigen Person verlangt, der Verfahrensleitung ohne Verzug ein entsprechendes Gesuch zu stellen, sobald sie vom Ausstandsgrund Kenntnis hat; die den Ausstand begründenden Tatsachen sind glaubhaft zu machen. Nach der Rechtsprechung ist der Ausstand in den nächsten Tagen nach Kenntnisnahme zu verlangen. Andernfalls verwirkt der Anspruch, was unbesehen des Umstands gilt, dass Ausstandsgründe von Amtes wegen zu berücksichtigen sind. Ein Gesuch, das sechs bis sieben Tage nach Kenntnis des Ausstandsgrunds eingereicht wird, gilt als rechtzeitig. Unzulässig ist jedenfalls ein Zuwarten während zwei Wochen (zum Ganzen: Urteil 1B_120/2019 vom 7. Juni 2019 E. 2.2 mit Hinweis).
2.3. Die Frage der Befangenheit eines Staatsanwalts ist entsprechend seiner sich wandelnden Funktion und Stellung im Rahmen des Strafverfahrens unterschiedlich zu beurteilen. Dabei ist in erster Linie zwischen dem Vorverfahren und dem gerichtlichen Verfahren zu unterscheiden. Im Vorverfahren gewährleistet die Staatsanwaltschaft eine gesetzmässige und geordnete Durchführung des Verfahrens (Art. 62 Abs. 1 StPO). Sie untersucht die belastenden und entlastenden Umstände mit gleicher Sorgfalt (Art. 6 Abs. 2 StPO). Nach Erhebung der Anklage wird sie dagegen wie die beschuldigte Person und die Privatklägerschaft zur Partei (Art. 104 Abs. 1 StPO). In diesem Verfahrensstadium ist die Staatsanwaltschaft definitionsgemäss nicht mehr zur Unparteilichkeit verpflichtet und hat sie grundsätzlich die Anklage zu vertreten (Art. 16 Abs. 2 StPO). Entsprechend kann sich der Angeklagte nicht über eine parteiische Haltung der Staatsanwaltschaft in den Verhandlungen beschweren (<ref-ruling> E. 3.2.2 S. 180 mit Hinweis). Allerdings bleibt die Staatsanwaltschaft auch als Prozesspartei der Objektivität verpflichtet. Sie darf somit keine Verurteilung um jeden Preis anstreben. Vielmehr hat sie für eine gerechte Anwendung des Strafgesetzes einzutreten. Auch als Partei darf sie daher nicht bewusst wesentliche Punkte weglassen oder wissentlich unwahre Tatsachen vorbringen (Urteil 1B_139/2018 vom 26. November 2018 E. 4.3; s. auch Urteil 6B_719/2017 vom 10. September 2018 E. 2.1; je mit Hinweisen). Der Unterschied zwischen Vorverfahren und Gerichtsverfahren ist insofern gradueller, nicht kategorischer Natur (vgl. HENRIETTE KÜFER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl., 2014, N. 20 zu Art. 104 StPO).
2.4. Verhält sich ein Staatsanwalt in einer Art und Weise, die mit dieser reduzierten Pflicht zur Objektivität nach der Anklageerhebung nicht mehr vereinbar ist und erblickt eine Verfahrenspartei darin einen Ausstandsgrund, so hat sie diesen gemäss Art. 58 Abs. 1 StPO ohne Verzug geltend zu machen. Dabei ist unbeachtlich, ob vorhersehbar ist, welchen weiteren Verlauf das Verfahren nehmen könnte. Das Argument des Beschwerdeführers, erst durch die Rückweisung der Sache ans Obergericht sei eine weitere Mitwirkung des Beschwerdeführers absehbar geworden und erst zu jenem Zeitpunkt habe es wieder ein kantonales Strafverfahren gegeben, verfängt aus diesem Grund nicht. Hinzu kommt, dass die Staatsanwaltschaft auch im bundesgerichtlichen Beschwerdeverfahren als Partei auftritt. Ein unverzüglich erhobenes Ausstandsgesuch wäre somit nicht unzulässig gewesen. Der Beschwerdeführer sah jedoch damals von einem solchen Vorgehen ab. Dass er in seiner Beschwerde ans Bundesgericht vom 16. April 2018 die Ausstandsproblematik thematisierte und für den Fall einer Rückweisung an die Staatsanwaltschaft beantragte, den Fall einer ausserordentlichen, neu einzusetzenden Staatsanwaltschaft zu übergeben, hat das Bundesgericht in seinem Urteil vom 14. Januar 2019 nicht als Ausstandsgesuch aufgefasst, was der Beschwerdeführer akzeptierte (s. Art. 121 lit. c BGG). Hinzu kommt, dass der Beschwerdeführer ohnehin nicht aufgezeigt hat, zu welchem genauen Zeitpunkt er von der Strafanzeige erfahren hat, weshalb nicht erstellt ist, dass ein am 16. April 2018 erhobenes Ausstandsgesuch noch als unverzüglich erfolgt hätte angesehen werden können.
Das Obergericht ist somit auf das erst am 25. Januar 2019 eingereichte Gesuch zu Recht nicht eingetreten.
3.
Die Beschwerde ist aus diesen Gründen abzuweisen, soweit darauf einzutreten ist.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG). Es ist keine Parteientschädigung zuzusprechen (Art. 68 Abs. 1-3 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien, der Staatsanwaltschaft II des Kantons Zürich und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. Januar 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Dold