Sachverhalt:
A. X._ (geb. 1952) und Z._ (geb. 1962) sind die geschiedenen Eltern von S._ (geb. 1996) und T._ (geb. 1999). Im Scheidungsurteil vom 8. September 2004 hatte das Bezirksgericht Winterthur nicht nur den persönlichen Verkehr zwischen Vater und Kindern geregelt, sondern auch eine Erziehungsbeistandschaft im Sinne von Art. 308 Abs. 1 und 2 ZGB angeordnet.
B. Mit Beschluss vom 29. Januar 2008 hob die Vormundschaftsbehörde der Stadt A._ die Beistandschaft gemäss <ref-law> auf und ernannte zugleich W._ zum neuen Beistand gemäss <ref-law>, nachdem die mit diesem Amt betraute Person seit 2005 bereits zweimal ausgewechselt worden war. Mit einem weiteren Beschluss vom 22. Dezember 2010 regelte die Vormundschaftsbehörde in Abänderung des Scheidungsurteils auch das Besuchsrecht zwischen X._ und seinen beiden Kindern neu.
C. Gegen diese vormundschaftlichen Beschlüsse setzte sich X._ in verschiedenen Verfahren zur Wehr. Ohne Erfolg beantragte er der Vormundschaftsbehörde, erneut eine Erziehungsbeistandschaft nach <ref-law> zu errichten, und ersuchte sie darum, dem Beistand W._ das Mandat zu entziehen und einen neuen Besuchsrechtsbeistand einzusetzen. Vor dem Bezirksrat Winterthur focht X._ auch die Änderung der Besuchsrechtsregelung an. Der Bezirksrat vereinigte dieses Beschwerdeverfahren mit den hängigen Beschwerden betreffend die Gesuche um Auswechslung des Besuchsrechtsbeistands W._ und um (Wieder-)Errichtung einer Erziehungsbeistandschaft für S._ und T._ und wies alle Begehren ab, soweit er auf die Beschwerden eintrat (Beschluss vom 26. August 2011).
D. Hierauf gelangte X._ an das Obergericht des Kantons Zürich. Dieses trat auf die als Berufung entgegengenommene Eingabe nicht ein, soweit X._ auf der "Wiedereinführung einer Erziehungsbeistandschaft" und auf seinem Begehren beharrte, den Besuchsrechtsbeistand auszuwechseln; bezüglich beider Punkte erwog es im Sinne einer Eventualbegründung, die Berufung wäre bei einer materiellen Prüfung ohnehin abzuweisen. Hinsichtlich der Besuchsrechtsregelung bestätigte das Obergericht den Beschluss der Vormundschaftsbehörde und wies die Berufung insofern ab.
E. Mit Eingabe vom 9. März 2012 (Datum der Postaufgabe) wendet sich X._ (nachfolgend Beschwerdeführer) nun an das Bundesgericht. In der Sache stellt er das Begehren, dem Beistand W._ unverzüglich das Mandat zu entziehen.
Das Bundesgericht hat die vorinstanzlichen Akten, aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Das Bundesgericht überprüft von Amtes wegen und mit freier Kognition, ob eine Beschwerde zulässig ist (<ref-ruling> E. 1 S. 216; <ref-ruling> E. 1 S. 117, je mit Hinweisen).
1.2 Die Beschwerde richtet sich einzig gegen die Verweigerung des Beistandswechsels. Streitig ist also eine nicht vermögensrechtliche vormundschaftliche Massnahme, mithin ein öffentlich-rechtlicher Entscheid, der in unmittelbarem Zusammenhang mit dem Zivilrecht steht und als Endentscheid von einer letzten kantonalen Instanz gefällt wurde (Art. 72 Abs. 2 lit. b Ziff. 6, Art. 75 und 90 BGG).
1.3 Die - hier massgebliche - ordentliche Beschwerdefrist beträgt 30 Tage nach Eröffnung der vollständigen Ausfertigung des Entscheids (<ref-law>). Die Frist beginnt am Tag zu laufen, der auf die Mitteilung des Entscheids folgt (<ref-law>), wobei eine Mitteilung, die nur gegen Unterschrift überbracht wird, spätestens am siebenten Tag nach dem ersten erfolglosen Zustellungsversuch als erfolgt gilt (<ref-law>).
Der angefochtene Entscheid war dem Beschwerdeführer am 25. Januar 2012 von der Schweizerischen Post zur Abholung gemeldet worden. Die siebentägige Frist gemäss <ref-law> endete somit am 1. Februar 2012, so dass die am 9. März 2012 der Schweizerischen Post übergebene Beschwerde eigentlich verspätet wäre. Allerdings hat Post die Abholungsfrist auf Gesuch des Beschwerdeführers bis zum 8. Februar 2012 verlängert; an diesem Tag hat der Beschwerdeführer den angefochtenen Entscheid auch abgeholt. Nun hat die Frage, wie lange eine Sendung bei der Post abgeholt werden kann, aber grundsätzlich keinen Einfluss auf den Zeitpunkt des Eintritts der gesetzlichen Zustellfiktion (<ref-law>), selbst dann nicht, wenn auf der Abholungseinladung eine andere als die siebentägige Frist vermerkt ist (Botschaft des Bundesrates vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege, BBl 2001 4297; <ref-ruling> E. 3b/aa S. 36). Nach der Rechtsprechung kann allerdings selbst von einem Juristen, der nicht Anwalt und auch nicht anwaltlich vertreten ist, nicht verlangt werden, die Unterscheidung zwischen dem Ende der postalischen Abholfrist und dem Ende der Legalfrist betreffend Zustellungsfiktion zu kennen (Urteile 1C_85/2010 vom 4. Juni 2010 E. 1.4.3; vgl. auch 2D_37/2010 vom 23. November 2010 E. 3.4). Unter Vertrauensgesichtspunkten darf daher auch dem Beschwerdeführer aus dem Auseinanderklaffen des Datums der Zustellfiktion (1. Februar 2012) und des letzten Tages der postalischen Abholfrist (8. Februar 2012) kein Nachteil erwachsen, weshalb die Beschwerde als rechtzeitig erhoben entgegenzunehmen ist.
1.4 Im ordentlichen Beschwerdeverfahren sind vor Bundesgericht in rechtlicher Hinsicht alle Rügen gemäss Art. 95 f. BGG zulässig. Das Bundesgericht wendet das Recht in diesem Bereich von Amtes wegen an (<ref-law>) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Rügen (<ref-ruling> E. 1.1 S. 104 f.; s. auch Urteil 5A_92/2008 vom 25. Juni 2008 E. 2.3). Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Der Beschwerdeführer muss auf den angefochtenen Entscheid eingehen und im Einzelnen aufzeigen, worin eine Verletzung von Bundesrecht liegt; er soll im Schriftsatz mit seiner Kritik an den Erwägungen der Vorinstanz ansetzen, die er als rechtsfehlerhaft erachtet (vgl. <ref-ruling> E. 2a S. 400; Urteil 4A_22/2008 vom 10. April 2008 E. 1). Allgemein gehaltene Einwände, die er ohne aufgezeigten oder erkennbaren Zusammenhang mit bestimmten Entscheidungsgründen vorbringt, genügen nicht (<ref-ruling> E. 3 S. 749).
2. 2.1 Zu klären wäre vor Bundesgericht an sich die Frage, ob das Obergericht auf die Berufung hätte eintreten müssen, die der Beschwerdeführer gegen den Entscheid des Bezirksrats erhoben hatte. Das Obergericht befand nämlich, weil die Berufungsschrift den Anforderungen an die Berufungsbegründung nicht genüge, sei auf die Berufung nicht einzutreten. Der Beschwerdeführer setzt sich damit nicht auseinander, sondern beschränkt sich darauf, an der Erforderlichkeit eines Beistandswechsels festzuhalten. Wie es sich mit dem Nichteintretensentscheid des Obergerichts verhält, kann letztlich offenbleiben, denn das Obergericht äussert sich nichtsdestotrotz auch zur Begründetheit des Gesuchs um Auswechslung des Besuchsrechtsbeistands und kommt zum Schluss, die Berufung wäre abzuweisen.
2.2 Das Obergericht erinnert daran, dass der Besuchsrechtsbeistand den Interessen der Kinder verpflichtet und nicht dazu da sei, die Vorstellungen des einen Elternteils gegenüber dem andern durchzusetzen. Deshalb könne sich der Beschwerdeführer grundsätzlich nicht darauf berufen, dass er sich ungenügend unterstützt fühle. Die Durchführung des Besuchsrechts hänge von unterschiedlichsten Faktoren ab, müsse stetig angepasst werden und verlange daher eine gewisse Flexibilität aller Beteiligten. Dass und inwiefern der Beistand die Interessen der Kinder nicht wahrgenommen hätte, werde nicht dargetan. Auch wenn dem Beistand im Einzelfall einmal ein Fehler unterlaufen wäre, nach Darstellung des Beschwerdeführers rund ein Viertel aller Besuchswochenenden nicht geklappt hätte und es auch bezüglich des Ferienbesuchsrechts dreimal zu grösseren Schwierigkeiten gekommen wäre, könne von vielen Fehlleistungen oder von einer unsorgfältigen Arbeitsweise des Beistandes nicht die Rede sein. Im Ergebnis seien weder Gründe für eine Amtsenthebung im Sinne von <ref-law> geltend gemacht worden noch lasse sich aus den erhobenen Vorwürfen ein Ungenügen im Sinne von <ref-law> konstruieren. Das Obergericht räumt ein, dass das Vertrauen des Beschwerdeführers in den Beistand zerrüttet ist und die Ablehnung eines Beistands eine erfolgreiche Amtsausübung beeinträchtigen könne. Dies allein genüge jedoch nicht, denn das Kindeswohl werde durch Kontinuität regelmässig besser gewahrt als durch einen durch die bisherige Amtsführung nicht gebotenen Wechsel. Dies gelte im vorliegenden Fall umso mehr, als bereits einmal auf Wunsch des Beschwerdeführers ein Beistandswechsel erfolgt und es auch weiteren Berufspersonen nicht gelungen sei, das Mandat zur Zufriedenheit des Beschwerdeführers auszuüben. Gestützt auf all diese Erwägungen kommt das Obergericht zum Schluss, dass die Berufung in der Sache abzuweisen wäre. Sollte sich allerdings in Zukunft herausstellen, dass die fehlende Vertrauensbasis zwischen Beistand und Kindsvater die Kindesinteressen ernstlich zu gefährden drohte, müsste ein Beistandswechsel in Betracht gezogen werden.
2.3 Gegen diese Beurteilung des Obergerichts vermag der Beschwerdeführer mit seinen Erörterungen nichts auszurichten. Zutreffend betont das Obergericht unter Hinweis auf <ref-law>, dass ein Beistand nur unter den in Art. 445 Abs. 1 und 2 ZGB aufgeführten Voraussetzungen abgesetzt werden kann. Was der Beschwerdeführer dem Bundesgericht vorträgt, um die Notwendigkeit eines Beistandswechsels zu belegen, erschöpft sich aber letztendlich in blossen Variationen über das von Misstrauen und Feindschaft geprägte Verhältnis zu seiner ehemaligen Ehefrau, deren Einflussbereich er den seiner Ansicht nach voreingenommenen Beistand zuordnet. Zu den konkreten Bedürfnissen und Interessen seiner Kinder, auf die es nach den zutreffenden Erwägungen des Obergerichts in erster Linie ankommt, äussert sich der Beschwerdeführer jedoch mit keinem Wort. Insbesondere setzt er sich auch nicht mit der vorinstanzlichen Feststellung auseinander, wonach er nicht dargetan habe, dass der Beistand die Interessen der Kinder nicht wahrgenommen hätte. Ebenso wenig zeigt er auf, inwiefern das fehlende Vertrauen zwischen ihm und dem Beistand die Kindesinteressen entgegen der Einschätzung des Obergerichts bereits im jetzigen Zeitpunkt ernstlich gefährde.
3. Nach dem Gesagten hält der angefochtene Entscheid vor Bundesrecht stand. Die Beschwerde erweist sich als unbegründet. Sie ist abzuweisen, soweit im Lichte von <ref-law> überhaupt darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer für die Gerichtskosten aufzukommen (<ref-law>). Der Beschwerdegegnerin sind keine entschädigungspflichtigen Aufwendungen entstanden (<ref-law>).

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 und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 25. Juni 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: V. Monn