Ukraine crisis: No sign of Russia withdrawal, says Nato
Nato and the US say there is no sign of a withdrawal of Russian troops from areas bordering Ukraine.
The Kremlin earlier announced units in the Rostov, Belgorod and Bryansk areas would return to their permanent bases.
Correspondents say removing some of the estimated 40,000 Russian troops could help de-escalate the Ukraine crisis.
Ukrainian government forces continue to clash with pro-Russia separatists who have taken over government buildings in southern and south-eastern Ukraine.
A statement from the Kremlin had said: "In connection with the completion of the planned spring phase of military training... at ranges in Rostov, Belgorod and Bryansk regions, [President Vladimir] Putin ordered the defence minister to withdraw the troops that took part in the exercises."
No indication was given as to troop numbers or a timetable.
However, Nato Secretary General Anders Fogh Rasmussen said: "Unfortunately, we have not seen any evidence at all that Russia has started withdrawal.
"I strongly regret that because a withdrawal of Russian troops would be a first important contribution to de-escalating the crisis."
Pentagon spokesman Rear Admiral John Kirby told Reuters news agency: "We have seen no indication of any movement."
One senior US official told Agence France-Presse that Washington would want to see "clear, firm evidence of this move before we make any judgement".
Russia has made two statements about withdrawals in the past.
Analysis: Jonathan Marcus, BBC Diplomatic correspondent
Some people may be wondering if there is a command and control problem in the Russian military. For this is actually the third time that Russian units have been ordered to pull back to their bases from their positions on Ukraine's border.
There was supposedly a partial withdrawal at the end of March. Only one battalion moved. A full withdrawal was ordered in early May but according to senior Nato military sources the troops are still very much there. Now a withdrawal order has come from the Kremlin again.
Of course there is nothing wrong with Russia's command system. President Vladimir Putin clearly decided that, whatever the public pronouncements, the threat of 40,000 troops on Ukraine's border was a powerful tool whether they were used or not.
This was by the way not the "planned spring phase of military training" as the Kremlin asserts but an unprecedented deployment of combat-ready forces designed specifically to threaten the Kiev government.
Air force drills
The Kremlin statement also reiterated Moscow's demand that the Kiev administration stop its military activities against the separatists and withdraws its troops.
Kiev said it was checking the reports of a Russian border withdrawal but also urged Moscow to call off an air force exercise planned for south-west Russia between Wednesday and Sunday, saying the drills would fuel tension ahead of Sunday's Ukrainian presidential election.
Two eastern Ukrainian regions - Donetsk and Luhansk - declared independence last week after a referendum.
The self-proclaimed Luhansk People's Republic on Monday said it would halt all preparations for the presidential election on its soil, deeming the poll "illegal".
Ukraine's PM Arseniy Yatsenyuk admitted polling in some eastern districts would be difficult, but added: "It affects very few areas... The election will take place and we will have a legitimate president."
Mr Putin has welcomed initial talks between Kiev and some of the separatists and has termed the presidential election a "step in the right direction".
However, violence continues in some parts of the east.
One Ukrainian soldier was killed and one injured on Monday in an attack by separatists on a checkpoint near Sloviansk, in the Donetsk region, Ukraine's Interfax news agency quoted the country's defence ministry as saying.
Tensions between Russia and the West rose after the overthrow of pro-Kremlin Ukrainian President Viktor Yanukovych in February, following months of street protests.
The revolt in the east gained momentum after Russia annexed Ukraine's mainly ethnic Russian region of Crimea in March.