Ukraine's Foreign Ministry has released a statement expressing its' "strong and categorical protest against the landing" of Russian troops in an area some 10 kilometers north of Crimea.
A statement issued by the ministry said some 80 troops of the "Russian Federation Armed Forces" backed by four helicopter gunships and three armored combat vehicles had seized the village of Strilkove in the Kherson region on March 15.
The ministry called it an "invasion" of Ukrainian territory and demanded Russia withdraw its forces immediately.
Ukrainian border guard spokesman Oleh Slobodan told the Associated Press news agency that some 120 Russian troops had taken control of a natural gas distribution station at Strilkove.
Ukraine's Foreign Ministry said Ukraine "reserves the right to use all necessary measures to stop the military invasion by Russia."
Ukraine's Defense Ministry released a statement earlier on March 15, claiming Ukrainian forces had repelled an attempt "by servicemen of the armed forces of the Russian Federation to enter the territory of the Kherson region on Arbatskaya Strelka."
However, as of the evening of March 15 it appeared from reports that the Russian troops were still at Strilkove and might have been reinforced during the course of the day.
An estimated 15,000 to 20,000 Russian troops remain in Crimea, where they have been for the past two weeks.
The United States Ambassador to the UN, Samantha Power called news of the Russian troop movement into Ukraine an "outrageous escalation" of the crisis.
Power was at the UN on March 15 for a Security Council vote on a draft resolution that would have declared the planned referendum on the status of Crimea invalid.
As expected, Russia vetoed the draft resolution at the Security Council vote.
China abstained, while the other 13 members of the Council voted in favor of the draft which said Crimea's vote on secession from Ukraine "can have no validity, and cannot form the basis for any alteration of the status of Crimea," and called on "all states, international organizations and specialized agencies not to recognize any alteration of the status of Crimea on the basis of this referendum."
After the resolution failed to be approved, Power said Russia might have the power to veto that resolution but could not alter the facts.
"Under the UN Charter, the Russian Federation has the power to veto a Security Council resolution but it does not have the power to veto the truth," she said.
Power also reiterated that Russia can expect to be punished for its actions in Crimea and eastern Ukraine.
"Russia cannot change the fact that moving forward in blatant defiance of the international rules of the road will have consequence, nor can it change Crimea's status," she said. "Crimea is part of Ukraine today, it will be part of Ukraine tomorrow, it will be part of Ukraine next week, it will be part of Ukraine unless and until its status is changed in accordance with Ukrainian and international law."
Meanwhile, Russian news agencies ITAR-TASS and Interfax have issued numerous reports about Russia's Foreign Ministry receiving "requests for protecting civilians" in Ukraine.
"Militants, including ones from the Right Sector, continue to commit outrages in Ukraine," Russia's Foreign Ministry said.
So far, no non-Russian news agencies have reported on any "outrages" against the population in eastern Ukraine.
With reporting by ITAR-TASS, Kanal 5 Ukraine, Reuters, AP, and Interfax