Sachverhalt: A. Mit Verfügung vom 1. April 2009 und Einspracheentscheid vom 16. Juli 2009 veranlagte die Eidgenössische Oberzolldirektion (OZD) die Nutzfahrzeuge der Y._ SA für die leistungsabhängige Schwerverkehrsabgabe betreffend Januar 2009 auf insgesamt Fr. 257'997.60. Dabei wandte sie den durch den Bundesrat per 1. Januar 2008 erhöhten Abgabetarif an sowie die ab 2009 vorgesehene Rückstufung sämtlicher Fahrzeuge der sog. "EURO-3-Norm"-Kategorie in eine teurere Abgabekategorie. Für die Berechnung der vom Schwerverkehr im Jahr 2009 zulasten der Allgemeinheit verursachten und ungedeckten sog. externen Kosten ging die OZD u.a. von 204 Mio. Franken Stau (zeitverlust) kosten und von 58 Mio. Franken Unfallkosten aus, bei einer gesamten Kostenunterdeckung (Ertrag der Schwerverkehrsabgabe minus Wegekosten und externe Kosten) von 19 Mio. Franken. B. Am 20. August 2010 wies das Bundesverwaltungsgericht eine Beschwerde der Y._ SA gegen den Einspracheentscheid vom 16. Juli 2009 ab, soweit es darauf eintrat. C. Mit Urteil 2C_751/2010 vom 17. Dezember 2011 wies das Bundesgericht die Sache zur weiteren Abklärung und Neubeurteilung an das Bundesverwaltungsgericht zurück. Dieses wurde angewiesen, (namentlich) die Staukosten in Übereinstimmung mit präzisen Vorgaben neu festzulegen (vgl. zum Verfahren betreffend die der Y._ SA für Januar 2008 auferlegte leistungsabhängige Schwerverkehrsabgabe das Urteil 2C_800/2009 vom 19. April 2010 bzw. das Parallelurteil in BGE 136 II 337 ff.). D. Am 24. Januar 2012 wies das Bundesverwaltungsgericht die OZD mit Zwischenverfügung an, die Stauzeitkosten für das Jahr 2009 in Übereinstimmung mit den bundesgerichtlichen Vorgaben zu beziffern und zu begründen. Die OZD kam dieser Anweisung dadurch nach, dass sie am 25. April 2012 eine Studie (sog. Studie "Infras 2012") vorlegte; danach beliefen sich die für das Jahr 2009 wesentlichen Staukosten gesamthaft auf 291 Mio. Franken und die Unfallkosten auf 149 Mio. Franken. Die Y._ SA legte eine Gegenstudie (sog. Studie "ProgTrans 2012") vor, wonach sämtliche Teilkosten jeweils deutlich tiefer waren, so dass für 2009 gesamthaft eine Kostenüberdeckung anzunehmen sei. E. Mit Urteil vom 22. Oktober 2012 hat das Bundesverwaltungsgericht eine Beschwerde der Y._ SA im Sinne der Erwägungen gutgeheissen: Zwar habe der Schwerverkehr (SV) dem Nichtschwerverkehr (NSV) im Jahr 2009 Staukosten von 94 Mio. Franken verursacht; da sich aber die in umgekehrter Richtung hervorgerufenen Staukosten auf 140 Mio. Franken belaufen hätten, liege diesbezüglich ein Kostenüberschuss vor. Weiter könnten die von der OZD geltend gemachten zusätzlichen Unfallkosten von 91 Mio. Franken (149 statt 58 Mio. Franken) im laufenden Verfahren nicht mehr berücksichtigt werden. F. Am 23. November 2012 hat die OZD Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht eingereicht. Sie beantragt, das bundesverwaltungsgerichtliche Urteil vom 22. Oktober 2012 aufzuheben und ihren Einspracheentscheid vom 16. Juli 2009 zu bestätigen. G. Die Y._ SA schliesst auf Abweisung der Beschwerde. Das Bundesverwaltungsgericht hat auf eine Vernehmlassung verzichtet. H. Am 19. Dezember 2012 hat der Präsident der II.-öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zuerkannt.