"Too many of us fell prey to the assumption that authoritarian regimes were a guarantee of stability in the region," continued Mr Fuele, the former Czech diplomat now in charge of EU enlargement and neighbourhood policy.

In a particularly blunt comment, he said that Europe should be standing with pro-democracy demonstrators and not "dictators" who are killing their citizens.

"The crowds in the streets of Tunis, Cairo and elsewhere have been fighting in the name of our shared values. It is with them, and for them, that we must work today - not with dictators who are, as we speak, spilling the blood of their own people with utter disregard for human life."

He said that Europe must react to developments in its southern neighbourhood the way that it did to similar uprisings against a different series of regimes in its eastern neighbourhood two decades ago: "Europe must and will rise to the challenge of supporting democratic transition in north Africa, as it did after the revolutions in Eastern Europe in 1989."

He added that concerns over increased migration, access to oil or the an "increased visibilty of Islamists" should not prevent Europe from supporting democracy in the region.

"Yes, there may be rising irregular migration flows originating from Tunisia, Libya and, to some extent, from Egypt. Yes, there will be a certain political vacuum in the newly democratising countries, including an increased visibility of Islamist parties and, at least in some of them, a worry that they may not want to play by the rules of democracy. Yes, there may be rising oil prices, lost investments and business. Yes, there may be potential civil war and instability in Libya."

"We know that the forces of change that have been unleashed will not produce stable political systems overnight. Yet, we must weather these risks without losing sight of our long-term common objective: a democratic, stable, prosperous and peaceful north Africa."

Mr Fuele said that the commission was now ready with a "new approach" that would match the level of ambition that the parliament has "consistently called for".

He announced that European Commission President Jose Manuel Barroso has asked all the different commission departments to identify what initiatives in their own areas can contribute to what he called "the new southern Mediterranean".

Mr Fuele and EU foreign policy chief Catherine Ashton will also issue a policy paper proposal on the subject on 16 March, which will then be considered by EU premiers and presidents at the spring European Council.

He signalled a fresh approach to the thorny question of migration from the region, saying that while the EU should continue to ask north African states to prevent irregular migration and co-operate on the return of refugees, he said the bloc should be "more ambitious" and floated the idea of legalised "temporary or circular migration" for workers.

He went on to say that Tunisia had made a request along these lines and that making it easier for workers to enter Europe on a legal basis was more desirable than having to deal with sudden mass exoduses.

"It is preferable to manage this type of migration rather than the humanitarian crises stemming from uncontrolled migration."

However, with an eye to member states that take a hardline perspective on immigration, he said he will need the help of the European Parliament if such strategies were to be embraced.

"This is another issue on which we will need the full support of this house," he said.

'North-south pact'

It is the first time an EU-level leader has offered an apology for the strategy. Catherine Ashton, the bloc's foreign policy supremo, has kept silent on the question of support for north African regimes.

Carl Bildt, Sweden's foreign minister, came close to making a similar assessment in January shortly after the Tunisian revolution when he wrote on his blog: "In the case of Tunisia, it is quite obvious that [European co-operation with north African states] failed."

"In retrospect, it is reasonable to ask whether we have been sufficiently robust in the requirements of respect also for democratic rights in Tunisia."

Finland's foreign policy chief, Alexander Stubb has also made critical remarks.

On Monday, Germany's foreign minister, Guido Westerwelle, also called for a new ‘north-south' pact between Europe and north Africa, echoing Mr Fuele's sentiment, if not quite so bluntly.

"First, it is being refuted more and more that, Islam, democracy and progress do not contradict themselves, and second, it is not via an autocratic government, but only by a stable society do we guarantee a stable country," he said, according to FT Deutchland.

France for its part has been repeatedly bludgeoned by commentators over the last two months as papers almost on a weekly basis have revealed fresh embarrassing ties between the French political class on both sides of the ideological spectrum and north African regimes.

In an attempt to staunch the bad press, France has been at the forefront of calls for stronger EU action over Libya. On Monday, Paris sent two planes to Benghazi, the eastern region of the country Prime Minister Francois Fillon is now describing as "liberated territory."

Announcing the move, he added: "And you will have seen that France was in the forefront of the decisions taken to sanction Colonel Gaddafi,"

"We were the ones who called on the European Council to adopt a joint position on this matter."

However, unlike in Algeria, Tunisia and Egypt, Paris has never had strong ties with the administration in Tripoli.

One EU diplomat last week explained how it is that more northerly countries within the Council have tended to be more critical of support for southern despots: "The further you are away from immigrants landing on your beaches, the more morally pure you can allow yourself to be."