I would like to exercise my right according to Directive/2004/38/EC to permanently move to Portugal with my wife.
The rule in question applies to all EU countries, but the way you tell it, the Portuguese consulate hasn't formally refused a visa, they have just suggested they cannot accept the application for a technical reason while being otherwise prepared to issue a visa.
You wrote that “Directive/2004/38/EC Article 5 only states that the passport has to be valid which it is” but the whole problem is that the Portuguese consulate apparently disagrees that your wife's passport is indeed valid (at least for this purpose). They might be wrong under Portuguese or EU law (personally I don't know that but it's possible) but juridically it's difficult to base a reasoning on the assumption that the passport is valid if they do not accept it.
Consider this: If your wife had no passport at all or a passport that was clearly and unambiguously expired, would they have to invoke “public policy, public security or public health” or “fraud” to decline to process an application? Having a valid passport is still required in any case!
All of this might or might not hold up in court but the consequence is that it's not obvious what rules are really at stake here. And obviously involving the courts would take a long time and is far from trivial. It's even more difficult if you don't have a formal refusal in the hand. Even something informal like SOLVIT (probably worth a try anyway) can take a few months so being right (if you are) does not immediately help you if the consulate does not want to see it.
Consequently, there aren't many practical solutions beyond pleading with the Portuguese or Guinean consulates and hoping one of them budges.
A few related ideas (all long shots, but certainly worth a try):
- Trying another embassy from Guinea Bissau, as suggested by @phoog in a comment. It does not seem very likely but the embassies in France or Belgium might be prepared to renew the passport without requiring the presence of your wife. Alternatively, the French or Belgium authorities might be prepared to disregard the current passport's validity extension problem or have a different interpretation than Portugal and issue a Schengen visa with which you could get a new passport or even go to Portugal.
- Asking Guinea Bissau to issue some sort of temporary passport/emergency travel document. I have no idea whether they do that at all but they could conceivably be less concerned about sending something like that per mail than a full passport and it would give them an excuse to go around their own rules while preserving appearances. You could then use that document to apply for a visa and go to Portugal with your wife to get a real passport.
- Showing up at the border for a ferry to France, as you suggest in a comment. Not very likely to succeed either because you have to show you have some “unforeseeable and imperative reasons for entry” but French border guards can legally issue a visa at the border for family members so it might work. Also, I don't know what they do if they decide to refuse entry (do they let you go or transfer you to UK border guards?) so you might want to be careful with that option if your wife's current status in the UK is uncertain.
Finally, as it seems that your situation is quite complex and precarious, I would urge you to seek professional legal advice.