Sachverhalt:
A. Dr. iur. X._ (Beschwerdeführer) ist Rechtsanwalt. Als solcher vertrat er A._, B._ und C._ (Beschwerdegegner) in einem Zivilprozess gegen D._ vor dem Zivilgericht Basel-Stadt. Dieser ging für die Beschwerdegegner ungünstig aus: Auf die Klage wurde nicht eingetreten, weshalb ihnen die Gerichtskosten und eine Parteientschädigung an die Gegenpartei auferlegt wurde.
B. Am 14. September 2010 machten die Beschwerdegegner gegen den Beschwerdeführer beim Bezirksgericht Zürich eine Klage anhängig mit dem Antrag, dieser sei zu verpflichten, ihnen Fr. 84'114.45 zu bezahlen. Sie begründeten die Klage damit, dass der Beschwerdeführer seinen Auftrag als Anwalt schlecht erfüllt habe. Gestützt darauf verlangten sie einerseits das dem Beschwerdeführer bezahlte Honorar zurück (Fr. 23'900.45), andererseits beanspruchten sie Ersatz der Gerichtskosten und der dem Prozessgegner bezahlten Parteientschädigung (insgesamt Fr. 60'214.--). Mit Urteil vom 5. Juli 2011 verpflichtete das Bezirksgericht den Beschwerdeführer, den Beschwerdegegnern Fr. 84'114.45 zuzüglich Zins zu 5% auf Fr. 23'900.45 seit 21. Juli 2008, auf Fr. 41'946.-- seit 4. August 2008 und auf Fr. 18'240.-- seit 27. Oktober 2008 zu bezahlen.
Gegen dieses Urteil erhob der Beschwerdeführer Berufung an das Obergericht des Kantons Zürich, das die Berufung am 6. Januar 2012 abwies und das erstinstanzliche Urteil bestätigte.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, das Urteil des Obergerichts mit Bezug auf die Verpflichtung des Beschwerdeführers zur Bezahlung von Fr. 23'900.45 zuzüglich Zins von 5% seit 21. Juli 2008 aufzuheben und die Klage der Beschwerdegegner insoweit abzuweisen (Ziff. 1). Die dem Beschwerdeführer von der ersten Instanz und der Vorinstanz auferlegte Verpflichtung zur Bezahlung von Gerichtskosten und Parteientschädigung sei dementsprechend angemessen zu reduzieren (Ziff. 2). Mit Rechtsbegehren Ziffer 3 beantragt er, die Beschwerdegegner seien zu verpflichten, ihm Fr. 28'016.65 (Honorar zuzüglich kapitalisierter Zins) zuzüglich Zins zu 5% seit 1. Februar 2012 zu bezahlen.
Die Beschwerdegegner beantragen, die Rechtsbegehren 1 und 2 der Beschwerde abzuweisen, soweit darauf eingetreten werde. Auf das Rechtsbegehren 3 der Beschwerde sei nicht einzutreten, eventualiter sei es abzuweisen, soweit darauf eingetreten werde. Die Vorinstanz verzichtete auf eine Vernehmlassung.
Die Parteien reichten Replik und Duplik ein.

Erwägungen:
1. 1.1 Das angefochtene Urteil des Obergerichts ist ein verfahrensabschliessender Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>). Sodann übersteigt der Streitwert, der sich nach den Begehren bestimmt, die vor der Vorinstanz streitig geblieben sind (<ref-law>) und rund Fr. 84'000.-- beträgt, die Grenze nach <ref-law>. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist - unter Vorbehalt einer hinlänglichen Begründung (Art. 42 Abs. 2 und <ref-law>) - grundsätzlich auf die Beschwerde einzutreten.
1.2 Nach <ref-law> sind neue Begehren unzulässig. Die Beschwerdegegner beantragen, auf das Rechtsbegehren Ziffer 3 nicht einzutreten, da es neu sei. Der Beschwerdeführer verlangt damit die Rückzahlung von Fr. 28'016.65 (Fr. 23'900.45 Honorar plus Fr. 4'116.20 kapitalisierter Zins). Er macht geltend, diesen Betrag den Beschwerdegegnern im Nachgang zum Urteil der Vorinstanz bezahlt zu haben, da die Beschwerde keine aufschiebende Wirkung habe.
Dieses Rechtsbegehren ist in der Tat neu. Es wird vor Bundesgericht erstmals gestellt und sprengt den Rahmen des Streitgegenstandes. Im Streit liegt die Frage, ob der Beschwerdeführer den Beschwerdegegnern das Honorar von Fr. 23'900.45 nebst Zins zurückzuerstatten hat oder nicht. Sollte der Beschwerdeführer mit seiner Beschwerde durchdringen, könnte er die Rückzahlung des Betrages (nebst Zins), den er seit dem Erlass des angefochtenen Urteils bezahlt haben will, nötigenfalls in einem weiteren Prozess zu erstreiten suchen. Er kann dies nicht mit einem neuen Begehren vor Bundesgericht verlangen. Auf das Rechtsbegehren Ziffer 3 ist daher nicht einzutreten.
2. 2.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht kann das Bundesgericht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.3.1; <ref-ruling> E. 2.2; <ref-ruling> E. 3.2 S. 444).
2.2 Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (<ref-law>). Kommt es zu einem zweiten Schriftenwechsel, darf der Beschwerdeführer die Replik nicht dazu verwenden, seine Beschwerde zu ergänzen oder zu verbessern (vgl. <ref-ruling> E. 3.3.4).
Soweit der Beschwerdeführer dies missachtet, können seine Ausführungen in der Replik nicht berücksichtigt werden.
2.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (vgl. <ref-ruling> E. 1.2; <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1, 462 E. 2.4). Soweit der Beschwerdeführer den Sachverhalt ergänzen will, hat er zudem mit Aktenhinweisen darzulegen, dass er entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (Urteile 4A_214/2008 vom 9. Juli 2008 E. 1.2, nicht publ. in: <ref-ruling>; 4A_470/2009 vom 18. Februar 2010 E. 1.2). Überdies ist in der Beschwerde darzutun, inwiefern die Behebung des gerügten Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (BGE <ref-ruling> E. 1.4.3).
3. Der Beschwerdeführer lässt das Urteil der Vorinstanz unangefochten, soweit diese eine Verletzung der anwaltlichen Sorgfaltspflicht bejahte und daher den Beschwerdegegnern Schadenersatz betreffend geleistete Gerichtskosten und Parteientschädigung zusprach. Er wendet sich einzig gegen die Verpflichtung zur Rückerstattung des mittels Vorschüssen bezogenen und einbehaltenen Honorars von Fr. 23'900.45 nebst Zins. Dabei bestreitet er nicht, dass das Honorar grundsätzlich zurückzubezahlen wäre. Er beharrt aber weiterhin auf dem Standpunkt, der Rückerstattungsanspruch sei bereicherungsrechtlicher Natur und daher verjährt.
3.1 Wird ein Auftrag nicht sorgfältig ausgeführt, kann dies zu einer Herabsetzung der Vergütung als vertraglicher Gegenleistung im Sinne von <ref-law> führen. Wenn das Ergebnis des unsorgfältigen Beauftragten für den Auftraggeber vollständig unbrauchbar ist, schuldet er diesem gar keine Vergütung (<ref-ruling> E. 4a S. 427; <ref-ruling> E. 2a S. 567; <ref-ruling> E. 2a; <ref-ruling> E. 4c S. 293; FELLMANN, Berner Kommentar, 1992, N. 501, 528 ff., insb. 540 zu <ref-law>; WEBER, in: Basler Kommentar, Obligationenrecht, 5. Aufl. 2011, N. 43 zu <ref-law>).
Der Beschwerdeführer stellt nicht in Abrede, dass seine Leistungen im Zusammenhang mit dem Prozess der Beschwerdegegner gegen D._ für die Beschwerdegegner insgesamt unbrauchbar waren, weshalb für diese keine Vergütung geschuldet ist und ein Rückforderungsanspruch grundsätzlich besteht.
3.2 Umstritten ist die Rechtsnatur dieses Rückforderungsanspruchs.
3.2.1 Die Vorinstanz qualifizierte ihn als vertraglicher Natur. Sie erwog, es sei nicht so, dass die Beschwerdegegner dem Beschwerdeführer nach Abschluss des Prozesses vor Zivilgericht Basel-Stadt in Kenntnis des Verfahrensausgangs ein Honorar bezahlt hätten, das sie nun zurückforderten. Vielmehr hätten sie dem Beschwerdeführer im Rahmen des Auftrags Akontozahlungen geleistet, und diese seien unter dem - wenn auch nur stillschweigend - vereinbarten Vorbehalt der Abrechnung gestanden. Der Beschwerdeführer räume ein, dass er zu viel erhalten habe. Das Zuviel habe er nach seiner Rechnung den Beschwerdegegnern zurückerstattet. Nun - so die Vorinstanz - erhöhe sich dieses Zuviel um das in Rechnung gestellte und einbehaltene Honorar von Fr. 23'900.45, und um diese Summe erhöhe sich die vertragliche Pflicht des Beschwerdeführers zur Rückgabe des akonto Geleisteten.
3.2.2 Wer ohne jeglichen Vorbehalt in (vermeintlicher) Erfüllung des Vertrags mehr leistet als das vertraglich Geschuldete, kann die Differenz auf der Grundlage des Bereicherungsrechts zurückfordern (<ref-ruling> E. 6.2; <ref-ruling> E. 3c/bb S. 426; je mit Hinweisen). Anders verhält es sich, wenn die Leistung in Form vertraglich vereinbarter Akontozahlungen erbracht, aber eine spätere Abrechnung vorbehalten wurde. In diesem Fall ist der Rückforderungsanspruch der zuviel geleisteten Akontozahlungen vertraglicher Natur (<ref-ruling> E. 6.4 S. 512; <ref-ruling> E. 3d). Diese Praxis wurde damit begründet, dass die Vereinbarung sowohl der Akontozahlung wie der Abrechnung auf dem Vertrag der Parteien beruht und daraus zu schliessen ist, dass diejenige Partei, die bei endgültiger Abrechnung zu viel erhalten hat, vertraglich zur Rückleistung der Akontozahlungen verpflichtet ist (BGE <ref-ruling> E. 3d). Demgegenüber ist auch im vertraglichen Abrechnungsverhältnis nach erfolgter und anerkannter Saldoziehung die Korrektur einer Fehlbuchung über das Bereicherungsrecht auszugleichen (<ref-ruling> E. 3.2.2). Diese Rechtsprechung gelangt namentlich bei zu viel bezahlten Mietnebenkosten zur Anwendung (Urteil 4C.24/2002 vom 29. April 2002 E. 3.3.2, in: mp 2002 S. 163 ff., 168).
3.2.3 Der Beschwerdeführer rügt eine Verletzung von Art. 1 und 67 OR. Die vorinstanzliche Erwägung, wonach die Akontozahlungen unter dem stillschweigend vereinbarten Vorbehalt der Abrechnung erfolgt seien, treffe nur insoweit zu, als es um die Beträge gehe, welche die Honorarrechnung überstiegen, nicht aber mit Bezug auf den infolge unsorgfältiger Mandatsführung weggefallenen Honoraranspruch. Diesbezüglich liege keine stillschweigend vereinbarte Abrechnungspflicht vor und der dahin gehende Rückforderungsanspruch sei daher nicht vertraglicher, sondern bereicherungsrechtlicher Natur.
Dem kann nicht gefolgt werden. Die Vereinbarung von Akontozahlungen enthält in der Regel die ausdrückliche oder stillschweigende Abrede auf Rückleistung eines Akonto-Überschusses. Die im Rahmen des Auftragsverhältnisses dem Beschwerdeführer von den Beschwerdegegnern bezahlten Honorarvorschüsse erfolgten demnach unter dem Vorbehalt der Rückforderung, soweit sie das effektiv geschuldete Honorar übersteigen würden. Ergibt sich - wie vorliegend -, dass wegen unsorgfältiger Mandatsführung, die zu einem für den Auftraggeber vollständig unbrauchbaren Resultat führte, überhaupt keine Vergütung geschuldet ist, erweisen sich die geleisteten Akontozahlungen insgesamt als überschiessende Zahlungen, die auf vertraglicher Basis zurückgefordert werden können. Dies erkannte die Vorinstanz zutreffend.
Die Argumentation des Beschwerdeführers scheitert aber auch unabhängig davon, ob die Abrechnungspflicht bezüglich Akontozahlungen den Rückerstattungsanspruch wegen unsorgfältiger Mandatsführung erfasst: Die vorliegende Situation ist nämlich vergleichbar mit derjenigen, wenn im Kauf-, Miet- oder Werkvertrag die Vergütung wegen Mängeln gemindert wird, um das Gleichgewicht im vertraglichen Austauschverhältnis wieder herzustellen. Die dabei entstehenden Rückerstattungsansprüche sind vertraglicher Natur (<ref-ruling> E. 6.5 S. 513; GAUCH, Der Werkvertrag, 5. Aufl. 2011, Rz. 1273) und unterstehen den entsprechenden Verjährungsfristen. Dasselbe gilt im Auftragsrecht für die Rückforderung des Honorars bei (teilweiser oder vollständiger) Unbrauchbarkeit der Leistung (vgl. Erwägung 3.1), ob der Auftraggeber nun wie hier Akontozahlungen geleistet oder aber ein Honorar in vereinbarter Höhe bezahlt hat. In beiden Fällen ist der Rückerstattungsanspruch des Auftraggebers vertraglicher und nicht bereicherungsrechtlicher Natur, und es gelten die vertraglichen Verjährungsfristen, ohne dass es darauf ankommt, ob die Parteien stillschweigend eine entsprechende Rückerstattungspflicht vereinbart haben.
3.3 Der Beschwerdeführer macht geltend, er habe in der Klageantwort darauf hingewiesen, dass die Beschwerdegegner die Rückzahlung des nicht gebrauchten Teils der Akontozahlungen entgegengenommen und auf seine Abrechnung vom 21. Juli 2008 hin nie remonstriert hätten. Das Bezirksgericht sei insofern auf dieses Vorbringen eingegangen, als es erwogen habe, der Beschwerdeführer habe nicht behauptet, die Honorarrechnung sei anerkannt worden, und weiter, ein unterlassenes Remonstrieren genüge dafür jedenfalls nicht. Das Bezirksgericht habe diese Rechtsauffassung jedoch mit keinem Wort begründet. Die Vorinstanz ihrerseits habe sich überhaupt nicht zum Vorbringen des Beschwerdeführers geäussert und deshalb den Gehörsanspruch (mangelnde Begründung) gemäss <ref-law> und Art. 6 Ziff. 1 EMRK verletzt.
Soweit sich der Vorwurf der Gehörsverletzung direkt an das Bezirksgericht richtet, kann darauf nicht eingetreten werden. Anfechtungsobjekt bildet einzig das Urteil der Vorinstanz und nicht dasjenige des Bezirksgerichts.
Aber auch der Vorinstanz kann keine Verletzung von <ref-law> bzw. von Art. 6 Ziff. 1 EMRK vorgeworfen werden. Der Beschwerdeführer legt in der Beschwerdeschrift nicht dar, dass er in der Berufung an seinen Vorbringen festgehalten oder geltend gemacht hätte, die Beschwerdegegner hätten seine Rechnung anerkannt. Seine diesbezüglichen ergänzenden Ausführungen in der Replik müssen unbeachtet bleiben (vgl. Erwägung 2.2.). Somit ist vor Bundesgericht davon auszugehen, der Beschwerdeführer habe in der Berufung nichts Entsprechendes vorgebracht. Folglich brauchte sich die Vorinstanz dazu auch nicht zu äussern, und sie hat ihre Begründungspflicht nicht verletzt.
3.4 Schliesslich beruft sich der Beschwerdeführer auf den zuletzt genannten Entscheid des Bundesgerichts 4C.24/2002. Er macht geltend, die Beschwerdegegner hätten gegen seine Honorarabrechnung vom Juli 2008 nicht remonstriert, sondern erst am 12. November 2009 den Friedensrichter angerufen. Daraus sei abzuleiten, dass sie die Rechnung zunächst stillschweigend akzeptiert hätten. Erst nach über einem Jahr hätten sie den Prozess gegen den Beschwerdeführer eingeleitet, in dem sie auch die Rückerstattung des Honorars verlangt hätten. Dann aber sei der Sachverhalt vergleichbar mit dem Urteil 4C.24/2002, wonach ein anerkannter, aber unrichtiger Saldo über das Bereicherungsrecht ausgeglichen werde.
Die Berufung auf das Urteil 4C.24/2002 scheitert bereits daran, dass vorliegend nicht von einer Saldoanerkennung ausgegangen werden kann. Laut erster Instanz machte der Beschwerdeführer nicht geltend, die Beschwerdegegner hätten seine Honorarrechnung vom Juli 2008 anerkannt. Ein unterlassenes Remonstrieren genüge dafür jedenfalls nicht. Die Vorinstanz äusserte sich dazu nicht, was sie - wie dargelegt (Erwägung 3.3) - mangels diesbezüglicher Vorbringen im Berufungsverfahren auch nicht musste. Entsprechend sind keine Umstände festgestellt, aus denen das Bundesgericht auf eine Saldoziehung und Anerkennung der Honorarrechnung vom Juli 2008 durch die Beschwerdegegner schliessen müsste. Weder haben die Beschwerdegegner die genannte Rechnung vorbehaltlos bezahlt, noch haben sie es unterlassen, sie innert einer vertraglich vereinbarten Frist zu beanstanden. Im verbindlichen Sachverhalt der Vorinstanz ist nicht einmal festgestellt, dass die Beschwerdegegner gegen die Rechnung vorerst nicht remonstriert hätten. Mangels Sachverhaltsrüge kann der Sachverhalt nicht entsprechend ergänzt werden (vgl. Erwägung 2.3). Ohnehin wäre fraglich, ob allein der Umstand, dass die Beschwerdegegner gegen die Rechnung vom Juli 2008 vorerst nicht remonstrierten, eine Anerkennung bedeuten soll, wie der Beschwerdeführer meint. Demnach vermag der Beschwerdeführer auch mit seiner auf das Urteil 4C.24/2002 gestützten Argumentation nicht durchzudringen.
Es bleibt somit dabei, dass der Rückforderungsanspruch der Beschwerdegegner vertraglicher Natur und noch nicht verjährt ist.
4. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 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. Der Beschwerdeführer hat die Beschwerdegegner für das bundesgerichtliche Verfahren mit insgesamt Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 17. Juli 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Kölz