Kein Grund zur Verzweiflung. Es ist so, wie Du es Dir vorher dachtest. Deine Nicht-EU Ehefrau hat dasselbe Recht wie Du, sich in Portugal aufzuhalten.
Es ist jedoch so, dass noch viele Einwanderungs- und Konsularbeamte sich nicht so gut im EU-Recht auskennen (das wird langsam alt...).
Ich würde zur EU web-site gehen
http://www.europa.euund dort dich zu der Seite durchklicken, die die EU-Gesetzestexte hat. Dort suchst Du nach den Bestimmungen, die sich mit dem Recht auf Aufenthalt der Unionsbürger und ihrer Familienangehörigen jedweder StA auf dem Territorium der EU befassen. Es gibt die Möglichkeit, diese auf Portugiesisch auszudrucken. Mit einem Marker streiche die wichtigen Stellen an und gehe damit, Euren Pässen, Arbeitsvertrag, Nachweis von Unterkunft und Krankenversicherung zur portugiesischen
ABH. Kein Problem, das Recht ist eindeutig auf Eurer Seite. Falls Deine Frau zu dem Zeitpunkt des Umzugs noch keinen deutschen
AT hat, dann kann es allerdings sein, das ein Einreise Visum nötig ist.
Viel Glück