Partial results showed the French rejected the constitution by 56% to 44%.
"This is certainly not an encouraging sign," Verheugen told public ARD television, but he added it was "not a catastrophe for the EU".
However Verheugen, who is also the EU's industry commissioner, said the outcome of the French referendum meant he was "not particularly hopeful" that Dutch voters will approve the constitution when they vote in a referendum on Wednesday.
European Presidents remarks
The president of the European Parliament, Spaniard Josep Borrell, also regretted the French rejection, but said "Europe continues and the institutions are working fully."
Reading from a statement in Madrid, he tried to sound upbeat and noted that nine of the 25 EU countries had approved the constitution -"almost half" the total.
Borrell said the European construction "has already seen tough moments and each time has managed to come out of them strengthened." He expressed confidence that, "again, we will find the means to advance the European Union."
The Former EU Commission president Romano Prodi said he was "enormously disappointed" with outcome of the vote, adding that Europe needed to listen to the signal sent by French voters.
"We need to reflect and listen to these signals of apprehension. But at the same time we need to continue tenaciously with the European project"
Romano Prodi, Former EU Commission president
"If that indeed is the result, I am enormously disappointed," Prodi, on a family holiday in Crete, was quoted as saying by his office.
"We need to reflect and listen to these signals of apprehension. But at the same time we need to continue tenaciously with the European project," said Prodi, who now leads Italy's centre-left opposition.
British Foreign Secretary Jack Straw said that the rejection of the EU constitution by French voters raised "profound questions" about the future of Europe and called for a period of reflection.
"The result raises profound questions for all of us about the future direction of Europe," Straw told reporters at the Foreign Office here shortly after exit polls showed that a French referendum had produced a 55% vote against the constitution.
"We need a period of reflection," he went on. France was 10th among the 25 members of the European Union to decide whether or not to ratify the constitution, and the first to reject it.
Asked whether Britain stood by its plan to hold a referendum on the treaty, Straw replied: "In the United Kingdom, this constitutional treaty will only be ratified by referendum."
But he hinted that the French result had already compromised the future of the treaty, saying:
"The decision about the future of the constitution is one for the European Council and for all 25 member states ... we haven't got to make a decision this evening and in my opinion it would be unwise to do so."
The British Prime Minister Tony Blair was not expected to comment on the French rejection of the EU constitution in a referendum before Monday morning, a government spokesman said.
A spokesman for the Italian Prime Minister Silvio Berlusconi's Forza Italia party said the French vote result "sounded a big alarm across Europe". Berlusconi himself was expected to comment on Monday.
Britian's Straw said the vote raised
questions over Europe's direction
Swedish Prime Minister Goeran Persson said the French rejection of the European constitution in a referendum Sunday was a setback for Europe.
"It is a setback for the French president and his government, it is a setback for the ratification process and it is an enormous setback for the prospects of Europe," Persson said on SVT1 public television.
He said the French rejection of the constitution was influenced by other considerations.
"The French were preoccupied by unemployment and unhappy with their president," said Persson, referring to Jacques Chirac.
"We'll decide for ourselves," said the prime minister when asked about Sweden's plans to hold a parliamentary vote to ratify the constitution this December.
Germany on Friday became the ninth country to ratify the constitution.
The treaty was overwhelmingly approved by both houses of the German parliament, but a referendum was not held.
Spanish Prime Minister Jose Luis Rodriguez Zapatero planned to speak to French President Jacques Chirac late on Sunday, Italian media said, quoting sources in Zapatero's office.
In the Netherlands, Premier Jan Peter Balkenende said he was disappointed with the French outcome, but that the opinion of the French electorate would be respected.
"The European ratification process will of course continue," he said in a televised address. "The French vote gives all the more reason [for the Dutch] to vote 'yes' because the constitution is the way forward."
"Every country has its own responsibility, and that means the Dutch voters will have to make up their own minds," he said. Despite the clear French vote, "it is far too soon" to speak of the demise of the charter.
"The French vote gives all the more reason [for the Dutch] to vote 'yes' because the constitution is the way forward"
Jan Peter Balkenende, Netherlands Premier
Dutch pollsters have said a French "no" could play into the hands of opponents of the constitution in the Netherlands.
In Eastern Europe, the reaction was greeted largely pessimistaically. The rejection of the treaty is likely to stoke fears of slower integration for Eastern Europe, unnerving markets and upsetting politicians working hard to bring their countries up to EU-speed.
Polands Foreign Ministry's saying "the victory of the "No" camp means the end of a European honeymoon for Poland".
Eastern Europe's hope
Slovenian Foreign Minister Dimitrij Rupel commented: "In France, and not only in France, there is a prevailing mentality that it is better to say no than yes. That means closing the door"
Both Latvia and Estonia said they would go ahead with ratification despite the French outcome. Latvia's parliament is to vote on the constitution on Thursday, while Estonia's lawmakers is expected to address it within the next month.
The constitution -more than two years in the making- is meant to be the EU's next big step in a 50-year process of bringing together nations and peoples divided by centuries of war.
It needs the backing of all 25 members to take effect in 2006. It would streamline EU decision-making and give the bloc a president and foreign minister, while larger countries like France and Germany would win greater say in EU decisions.
Chirac's vision for Europe has been
Opponents have voiced loud objections fearing it will lead to a loss of sovereignty and an influx of cheap labor from new Eastern European members.