US Secretary of State Hillary Clinton has told a meeting of Nato foreign ministers in Brussels it is time for a "fresh start" with Russia.

She spoke as ministers debated resuming formal relations with Moscow which Nato froze after the brief war last summer between Russia and Georgia.

Mrs Clinton said that areas of common interest included Afghanistan.

But she added that Nato must leave open the door to membership for Georgia and fellow ex-Soviet state Ukraine.

Earlier, Russia's envoy to Nato defended the war against Georgia and said any new relationship with Nato would be on Moscow's own terms.

Nato remains the central pillar of the trans-Atlantic relationship but it is facing a critical military and political challenge in Afghanistan, where failure could call into question its whole credibility, BBC diplomatic correspondent Jonathan Marcus reports from Brussels.

US foreign policy is now very much a team game and US Vice-President Joe Biden will be in Brussels next Tuesday for a more detailed exchange of views on Afghanistan, our correspondent adds.

"It's time to explore a fresh start," Mrs Clinton said.

"We can and must find ways to work constructively with Russia where we share areas of common interest, including helping the people of Afghanistan."

"We should continue to open Nato's door to European countries such as Georgia and Ukraine and help them meet Nato standards," she added.

Earlier, Nato Secretary General Jaap de Hoop Scheffer called on ministers to back "a positive agenda that befits the importance of Nato and Russia to European and indeed global security".

Nothing that "serious differences of opinion remain between Nato and Russia, in particular about Georgia", he listed as area of common interest Afghanistan, but counter-terrorism and non-proliferation.

UK Foreign Secretary David Miliband called for the resumption of formal ties with Russia through the Nato-Russia council.

"Russia needs the West as much as the West needs to re-engage with Russia," he said.

Some, like Germany and France, have long been pressing for the resumption of ties, arguing that their suspension has been counter-productive.

"We will not block because there are lots of issues Nato and Russia need to co-operate on, like transit to Afghanistan, Iran, the Middle East, non-proliferation," said Estonian Foreign Minister Urmas Paet.

However, his Lithuanian counterpart, Vygaudas Usackas, said he believed it was "premature to open the formal dialogue".

Dmitry Rogozin, Russia's permanent envoy to Nato, predicted an outcome of the Brussels talks "that should, on the whole, satisfy Russia" but made clear he saw Moscow negotiating from a position of strength.

 "We came out of the crisis that we had after the August 2008 events, the crisis in the South Caucasus, stronger,"he told Russian channel Vesti TV.

"Our Western colleagues saw in Russia a partner that one cannot wipe one's feet on. We are strong... and we are restoring cooperation, including on our terms."

Nato will, nonetheless, be trying to show that more normal business with Russia does not mean that the alliance is abandoning countries like Georgia and Ukraine, our correspondent says. Their foreign ministers will be in Brussels too.

Story from BBC NEWS