Sachverhalt:
A. A.a X._, schweizerische Staatsangehörige mit Wohnsitz in der Schweiz, absolvierte die Physiotherapieschule Bad Säckingen in Baden-Württemberg (Deutschland) und erhielt am 14. Juli 1997 die Erlaubnis zur Führung der Berufsbezeichnung "Physiotherapeutin". Am 26. Juli 1999 stellte das Schweizerische Rote Kreuz (SRK) X._ einen Anerkennungsausweis aus, wonach diese als "diplomierte Physiotherapeutin" registriert werde. Seit 2000 arbeitete sie in verschiedenen Stellen in der Schweiz als Physiotherapeutin. Im Jahre 2011 absolvierte sie an der Berner Fachhochschule Gesundheit den Nachdiplomkurs "wissenschaftliche Vertiefung in Physiotherapie" mit einem Umfang von 10 ECTS-Credits.
A.b Mit Gesuch vom 14./15. September 2011 beantragte X._ beim Bundesamt für Berufsbildung und Technologie (BBT; heute: Staatssekretariat für Bildung, Forschung und Innovation, SBFI) den nachträglichen Erwerb des Fachhochschultitels. Mit Verfügung vom 14. Oktober 2011 trat das BBT auf das Gesuch nicht ein (recte: wies es das Gesuch ab), da X._ kein entsprechendes Diplom einer vom SRK anerkannten schweizerischen Schule nachweisen könne.
B. X._ erhob dagegen Beschwerde an das Bundesverwaltungsgericht mit dem Antrag, es sei ihr in Aufhebung der angefochtenen Verfügung und in Gutheissung ihres Gesuchs vom 15. September 2011 nachträglich der Fachhochschultitel "dipl. Physiotherapeutin FH" zu erteilen. Mit Urteil vom 22. Oktober 2012 hiess das Bundesverwaltungsgericht die Beschwerde gut, hob die angefochtene Verfügung auf und wies die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurück.
C. Mit Eingabe vom 30. November 2012 erhebt das Eidgenössische Volkswirtschaftsdepartement (EVD; heute: Eidgenössisches Departement für Wirtschaft, Bildung und Forschung, WBF) beim Bundesgericht Beschwerde mit dem Antrag, das Urteil des Bundesverwaltungsgerichts aufzuheben und die Verfügung des BBT vom 14. Oktober 2011 zu bestätigen. Das Bundesverwaltungsgericht verzichtet auf Vernehmlassung. Das SBFI unterstützt die Beschwerde des Departements. X._ beantragt, auf die Beschwerde nicht einzutreten, eventuell sie abzuweisen.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den angefochtenen Entscheid des Bundesverwaltungsgerichts ist grundsätzlich zulässig (Art. 82 lit. a und Art. 86 Abs. 1 lit. a BGG). Ein Ausnahmegrund liegt nicht vor, namentlich nicht derjenige von Art. 83 lit. t BGG, da es nicht um die Beurteilung einer individuellen Fähigkeit geht, sondern um die Voraussetzungen zur Tragung eines Berufstitels aufgrund einer bestimmten Ausbildung (vgl. <ref-ruling> E. 1.2; Urteile 2C_417/2011 vom 13. Januar 2012 E. 1; 2C_731/2010 vom 16. November 2011 E. 1.1.3). Das Departement ist aufgrund von Art. 89 Abs. 2 lit. a BGG zur Beschwerde legitimiert.
1.2 Der angefochtene Entscheid ist ein Rückweisungsentscheid und damit ein Zwischenentscheid, der nur unter den Voraussetzungen von Art. 92 oder 93 BGG beim Bundesgericht anfechtbar ist (<ref-ruling> E. 4). Weist ein Gericht eine Sache mit verbindlichen Vorgaben zur neuen Beurteilung an eine Behörde zurück, so stellen diese Vorgaben für die Behörde einen nicht wieder gut zu machenden Nachteil (Art. 93 Abs. 1 lit. a BGG) dar, weil sie entgegen ihrer Rechtsauffassung einen Entscheid erlassen müsste, den sie in der Folge nicht mehr anfechten kann (<ref-ruling> E. 5.2.4). Dies gilt gemäss Rechtsprechung auch für Behörden, die auf einen Rückweisungsentscheid hin nicht selber neu verfügen müssen, wenn sie in der interessierenden Sache zwar beim Bundesgericht beschwerdebefugt sind, nicht jedoch bei der dem Bundesgericht vorgelagerten Instanz (Urteile 2C_258/2008 vom 27. März 2009 E. 3.6.2; 8C_969/2008 vom 2. März 2009 E. 3.2; 2C_420/2008 vom 3. Februar 2009 E. 4.5.2 und 2C_275/2008 vom 19. Juni 2008 E. 1.2). Vorliegend hätte das SBFI die neue Verfügung zu erlassen; das Departement könnte dessen Entscheid nicht beim Bundesverwaltungsgericht anfechten; es kann daher grundsätzlich gegen den angefochtenen Rückweisungsentscheid Beschwerde erheben (Art. 37 VGG i.V.m. Art. 48 VwVG; Art. 61 Abs. 2 des Bundesgesetzes vom 13. Dezember 2002 über die Berufsbildung [Berufsbildungsgesetz, BBG; SR 412.10]; Urteil 2C_275/2008 vom 19. Juni 2008 E. 1.2).
1.3 Dies gilt aber nur, soweit der Rückweisungsentscheid materiellrechtliche Vorgaben enthält, welche die untere Instanz bei ihrem neuen Entscheid befolgen muss. Erschöpft sich der Rückweisungsentscheid in der Aussage, dass eine Frage ungenügend abgeklärt erscheine und deshalb näher zu prüfen sei, ohne dass damit materiellrechtliche Vorgaben verbunden sind, so entsteht der Behörde, an die zurückgewiesen wird, kein nicht wieder gut zu machender Nachteil, führt die Rückweisung doch bloss zu einer dieses Kriterium nicht erfüllenden Verlängerung oder Verteuerung des Verfahrens (<ref-ruling> E. 1.2.1; <ref-ruling> E. 5.2.2; Urteil 8C_190/2011 vom 13. Februar 2012 E. 3, nicht publ. in <ref-ruling>; Urteile 8C_400/2012 vom 28. Juni 2012 E. 2.2; 2C_258/2008 vom 27. März 2009 E. 3.5, StE 2009 B 96.21 Nr. 14; HANSJÖRG SEILER, Rückweisungsentscheide in der neueren Sozialversicherungspraxis des Bundesgerichts, Sozialversicherungsrechtstagung 2008, S. 32 f.). Dasselbe gilt, wenn ein Rückweisungsentscheid zwar einige materielle Teilfragen beantwortet, aber nur solche, die von der Beschwerde führenden Behörde gar nicht beanstandet werden, und in anderen Punkten zu neuer Prüfung ohne materielle Vorgaben zurückweist. Denn in diesem Fall entsteht für die Behörde kein nicht wieder gut machender Nachteil, so dass kein Anlass besteht, auf die Beschwerde einzutreten. Damit lässt sich auch die Problematik vermeiden, dass das Bundesgericht materielle Rechtsstandpunkte zum Nachteil der privaten Gegenpartei bestätigt, welche den Rückweisungsentscheid nicht anfechten konnte (vgl. dazu <ref-ruling> E. 2.2; SEILER, a.a.O., S. 37 ff.).
1.4 Streitthema ist vorliegend, ob die Beschwerdegegnerin die Voraussetzungen für den (nachträglichen) Erwerb des Fachhochschultitels gemäss Art. 1 Abs. 3 der Verordnung des EVD vom 4. Juli 2000 über den nachträglichen Erwerb des Fachhochschultitels (SR 414.711.5) erfüllt, wobei einzig die Voraussetzung nach lit. a dieser Bestimmung (Diplom einer vom SRK anerkannten Schule) umstritten ist.
Die Vorinstanz erwog zunächst, die Schule Bad Säckingen sei im Zeitpunkt, in dem die Beschwerdegegnerin ihr Diplom erworben habe, nicht vom SRK anerkannt gewesen, weshalb die streitige Voraussetzung nicht erfüllt sei (E. 4). Sodann verneinte sie einen Anspruch auf den Fachhochschultitel aus Treu und Glauben (E. 5). Ebenso verneinte sie eine Verletzung der Wirtschaftsfreiheit (E. 7). Bezüglich der von der Beschwerdegegnerin erhobenen Rüge der Verletzung des Gleichheitsgebots (Art. 8 Abs. 1 BV) führte die Vorinstanz aus, eine allfällige Gleichbehandlung müsse mit Blick auf das Verhältnis zwischen der Beschwerdeführerin (bzw. heutigen Beschwerdegegnerin) und Diplomierten der Physiotherapieschule Bad Säckingen, welche dort das zusätzliche vierte Ausbildungsjahr absolviert hätten, geprüft werden. Es stelle sich die Frage, ob sich das von den Diplomierten der späteren Jahrgänge abgeschlossene zusätzliche Ausbildungsjahr inhaltlich und qualitativ mit dem zusätzlichen Praxisjahr gleichsetzen lasse, welches die Beschwerdeführerin nach ihren Angaben im Hinblick auf die Anerkennung ihres Abschluss durch das SRK habe vorweisen müssen. Diese Frage könne anhand der vorliegenden Akten nicht beantwortet werden, sondern es bedürfe dazu ergänzender tatsächlicher Feststellungen, die wegen ihrer fachtechnischen Natur nicht durch das Bundesverwaltungsgericht vorzunehmen wären (E. 6.5.1). Falls sich das Praxisjahr als gleichwertig herausstellen sollte, bliebe in tatsächlicher Hinsicht zu prüfen, ob das SRK mit der Anerkennung des vierten Ausbildungsjahres auch die Physiotherapieschule Bad Säckingen als solche anerkannte; ein Stempel des SRK auf entsprechenden Diplomen dürfte diese Anerkennung indizieren (E. 6.5.2). Die Darstellung des BBT, wonach das von der Beschwerdeführerin absolvierte Ausbildungsprogramm vom SRK nicht geprüft worden sei, scheine mindestens ungenau zu sein, da laut Anerkennungsausweis das SRK die Ausbildung und Berufskenntnisse der Beschwerdeführerin vor ihrer Registrierung als dipl. Physiotherapeutin geprüft habe. Worin die Prüfung im Einzelnen bestanden habe, gehe aus dem Anerkennungsausweis nicht hervor (E. 6.5.3). Zusammenfassend habe das BBT den Sachverhalt hinsichtlich verschiedener für die Beurteilung einer etwaigen Gleichbehandlung relevanter Aspekte zu wenig abgeklärt. Angesichts des überwiegend fachtechnischen Charakters seien die gebotenen ergänzenden Abklärungen durch das BBT vorzunehmen (E. 6.6).
1.5 Das Beschwerde führende Departement äussert sich mit keinem Wort zum Vorliegen der Voraussetzungen zur ausnahmsweisen Anfechtung von Rückweisungsentscheiden (vgl. vorne E. 1.2 und E. 1.3). Es stellt auch nicht die materiellen Aussagen der Vorinstanz in den E. 4, 5 und 7 des angefochtenen Entscheides in Frage, sondern beanstandet nur die Verpflichtung, eine Verletzung des Rechtsgleichheitsgebots zu prüfen. Es macht geltend, zwischen dem Abschluss der Beschwerdegegnerin und dem der Absolventen ab 1999 bestünden Unterschiede, die eine identische Titelvergabe nicht rechtfertigen würden. Das Bundesverwaltungsgericht verkenne zudem, dass die gesamtschweizerische Anerkennung einer Ausbildungsstätte durch das SRK (im Sinne von Art. 1 Abs. 3 lit. a Ziff. 1 der Verordnung) und die Prüfung der Gleichwertigkeit eines ausländischen Abschlusses auf unterschiedlichen Verfahren und Zielsetzungen beruhten. Massgebend für die nachträgliche Erteilung des Fachhochschultitels könne nicht das Ergebnis der vom Bundesverwaltungsgericht verlangten Prüfung der Gleichwertigkeit des Abschlusses der Beschwerdegegnerin aus dem Jahre 1997 mit den ab 1999 erfolgten Ausbildungsabschlüssen sein. Massgebend sei, dass die Diplome der Schule Bad Säckingen erst ab 1999 den Status eines Diploms einer vom SRK anerkannten Schule erlangt hätten. Es könne nicht Gegenstand des nachträglichen Erwerbs eines Fachhochschultitels sein, vorfrageweise zu prüfen, ob ein Abschluss mit dem zum Erwerb des Fachhochschultitels berechtigenden Abschluss vergleichbar sei.
1.6 Die Erwägungen der Vorinstanz können in der Tat den Eindruck erwecken, dass nicht unterschieden wird zwischen der Frage, unter welchen Umständen eine (ausländische) Ausbildung zur Berufsausübung in der Schweiz berechtigt (was Gegenstand der durch das SRK erfolgten Registrierung der Beschwerdegegnerin war) und der hier einzig zur Diskussion stehenden Frage, unter welchen Voraussetzungen der Fachhochschultitel nachträglich erworben werden kann. Indessen hat die Vorinstanz diesbezüglich keine materiellen Vorgaben gemacht: Sie hat die Angelegenheit einzig zur Prüfung einer "etwaigen Gleichbehandlung relevanter Aspekte" (E. 6.6 des angefochtenen Entscheids) zurückgewiesen, aber nicht festgelegt, was mit dem Ergebnis einer solchen Prüfung zu geschehen habe und was die Konsequenz wäre, wenn sich erweisen sollte, dass die von der Beschwerdegegnerin absolvierte Ausbildung mit der ab 1999 in der Schule Bad Säckingen angebotenen als gleichwertig erscheint. Insbesondere hat sie nicht verbindlich festgelegt, dass in diesem Fall der Beschwerdegegnerin der Fachhochschultitel zu erteilen sei. Unter diesen Umständen kann nicht gesagt werden, dass der angefochtene Entscheid materiellrechtliche Vorgaben enthält, welche die untere Instanz bei ihrem neuen Entscheid befolgen muss.
2. Auf die Beschwerde kann aus diesen Gründen nicht eingetreten werden. Das Departement trägt keine Gerichtskosten (Art. 66 Abs. 4 BGG), hat aber der Beschwerdegegnerin für das bundesgerichtliche Verfahren eine Parteientschädigung zu bezahlen (Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Es werden keine Gerichtskosten erhoben.
3. Das Eidgenössisches Departement für Wirtschaft, Bildung und Forschung hat der Beschwerdegegnerin für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 2'000.-- zu bezahlen.
4. Dieses Urteil wird den Parteien, dem Staatssekretariat für Bildung, Forschung und Innovation sowie dem Bundesverwaltungsgericht, Abteilung II, schriftlich mitgeteilt.
Lausanne, 25. April 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Klopfenstein