The treaty, which bans trade, economic, financial, transport, and other links with Abkhazia, was signed by 12 members of the CIS.
Georgia and Abkhazia have been locked in a protracted standoff over the region's ambitions to split from Georgia.
Georgian President Mikheil Saakashvili has made a political priority of returning to Georgian control Abkhazia and a second breakaway region, South Ossetia. But both regions receive financial and political support from Russia and have recently used Kosovo's independence declaration to launch their own bids for self-declared independence.
Georgian parliament speaker Nino Burjanadze, reacting to Russia's decision to withdraw from the treaty, says Tbilisi was caught "by surprise" by the "very bad news."
Burjanadze told RFE/RL in Brussels that Georgia had been optimistic that the two countries were making headway toward improving their rocky relationship.
However, she says, Georgia can only interpret Russia's withdrawal from the CIS treaty as a move toward Russia's formal annexation of Georgian territory.
"When they [Russia] are saying they are stopping [the] economic embargo [against] Abkhazia, it means that they are going, step by step, in the direction of the annexation of this territory. This is nothing if not an attempt of annexation," Burjanadze said on March 7.
In its statement to the CIS Executive Committee on March 6, Russia said the rationale for its decision to withdraw from the treaty was to induce Abkhazia to adopt a more flexible position with regard to the return of Georgian displaced persons to their homes in Abkhazia. The statement noted that most Georgians who wished to return have done so, and that the primary obstacle to others doing so is Georgia's refusal to agree to the rules for their registration proposed by the UN High Commissioner for Refugees.
The statement also said that, unlike Georgia, Abkhazia is "fulfilling its obligations" on conflict resolution, and is ready for "practical steps for strengthening confidence and security in the conflict zone." Russia called on other CIS members states to follow suit.
But Burjanadze says she sees other designs behind Russia's move, and expects Moscow to openly start supplying Abkhaz separatists with weapons and other supplies. Russia has already issued passports to a majority of residents in Abkhazia and South Ossetia -- a tactic that Burjanadze describes as "illegal."
She also believes the move can be seen as the Kremlin's response to Kosovo's recent declaration of independence from Serbia, a Russian ally. The Kremlin was fierce in its opposition to the West's support for Kosovo's move, and warned repeatedly that it could set a dangerous precedent for other separatist conflicts.
During his annual start-of-the-year news conference on January 23, Russian Foreign Minister Sergei Lavrov said that "many people assume that Russia has such a firm position on Kosovo and warns that [its declaration of independence] will set a precedent just because it [secretly wants this] to happen in order to begin recognizing" other regions declaring independence near Russia. But he insisted that "the Russian leadership has never said that after Kosovo we will immediately recognize Abkhazia and South Ossetia."
However, Russia's conciliatory statements have increasingly been replaced with tough talk since Kosovo's declaration of independence on February 17 -- placing the Western darling Georgia in the middle of the fray.
"Russia now is using the politics of sticks and carrots toward Georgia. It gives certain hopes and concessions -- be it the softening of various sanctions imposed on Georgia, or its statements about not transferring the Kosovo 'precedent,' Archil Gegeshidze, a Tbilisi-based political analyst, tells RFE/RL. "But in another hand it is holding a stick, and is trying to also hurt you."
Parliament speaker Burjanadze also said the timing of the Russian move was carefully gauged to coincide with the March 6 NATO debate in Brussels on whether to grant Georgia a Membership Action Plan (MAP).
"This is [a message] which was not sent only to Georgia, but to NATO member countries [whose foreign ministers were meeting in Brussels], and the main goal of Russia here is to create obstacles on our way to NATO," Burjanadze said.
Germany, France, and other NATO skeptics of closer ties with former Soviet countries such as Georgia argue the alliance cannot afford to "import" any of their so-called "frozen conflicts."
Burjanadze told RFE/RL that as one of Moscow's foreign-policy priorities is to halt NATO's expansion, Russia will do "everything, all the time, to keep these conflicts unresolved."
She also said Georgia feels "frustration" at what she described as Russia's "unpredictability."
"What is the main problem of Georgian-Russian relations? The main problem is that Russia is unpredictable," Burjanadze said.
Analyst Gegeshidze, however, says the Russian Duma's decision to withdraw from the 1996 CIS agreement banning trade, economic, financial, transport, and other links with Abkhazia, was not so surprising.
"This is an unfriendly move from Russia's side towards Georgia, however not an unexpected one, in light of general situation, and the background of Kosovo in particular," Gegeshidze says.
Russia's decision to lift the embargo on Abkhazia will likely have negative repercussions on Moscow's efforts to gain Georgia's approval for Russia's entry into the World Trade Organization (WTO).
Georgia, a member of the WTO, has blocked Russian accession, demanding Russia first establish customs and border control checkpoints on its borders with Abkhazia and South Ossetia. Any such deal would also commit Russia to accommodating for and securing the presence of Georgian officials at the same checkpoints.
Burjanadze said that hopes had been high in Tbilisi that such a deal could be achieved after recent top-level meetings between Russian and Georgian officials. But, she said, as on a number of occasions before, Russia now appears to have backtracked on commitments made at recent meetings.
Meanwhile, two Georgians held in jail for more than a week in Abkhazia have been released despite charges by authorities in the de facto republic that they illegally crossed the unrecognized border.
The detentions had further inflamed tensions between Tbilisi and the separatist leadership in Sukhumi.
Television stations in Georgia broadcast live footage of Malkhaz Basilaia and Davit Tsotsoria being escorted by Georgian peacekeepers across the Enguri Bridge that links Abkhazia to Georgia proper.
Basilaia, Tsotsoria, and Tsotsoria's mother were arrested on February 26 in Abkhazia's Gali district, which is predominantly populated by ethnic Georgians. They were placed in prison in the Abkhaz capital, Sukhumi. Tsotsoria's mother was released on March 1, but Tsotsoria and Basilaia, a television reporter, remained in detention until March 6, charged with "illegally crossing the Abkhaz border."
Abkhaz leader Sergei Bagapsh told reporters there were no additional charges pending against the two men, and were free to be released after 10 days.
In his first statement after being released, Basilaia claimed he had endured harsh treatment during the 10-day detention.
"For 10 days, we went through suffering [and] torture, but we never lost hope in our government, in our people, that they would not let us down and leave us there by ourselves," Basilaia said. "I was put in solitary confinement for three days, then they moved me to an ordinary cell."
Tsotsoria, by contrast, had no complaints about his treatment, saying that "the Abkhaz treated us very well" and "did not pressure us in any way."
Georgian President Mikheil Saakashvili had issued a strict ultimatum to the Abkhaz authorities while Basilaia was still in detention, saying Georgian police would forcibly retrieve the journalist from jail if he was not released. Abkhaz authorities said the ultimatum only resulted in prolonging Basilaia's and Tsotsoria's detention.
RFE/RL correspondents Salome Asatiani and Geronti Kalichava contributed to this report.