Just days after the summit concluded, Ukrainian President Viktor Yushchenko announced a public-relations campaign aimed at selling a skeptical public on the benefits of joining the trans-Atlantic alliance.
These two presidential announcements represent clear attempts by Tbilisi and Kyiv to address key weak spots in their respective NATO bids.
At their summit in the Romanian capital on April 2-4, the trans-Atlantic bloc's 26 heads of state stopped short of granting Georgia and Ukraine Membership Action Plans (MAP) -- a key step before joining. They postponed that decision until at least December, when NATO foreign ministers are due to meet.
"It is a political decision of the 26 whether or not to offer a Membership Action Plan. And they will take, and they are taking account of the broadest range of practical and political considerations," NATO spokesman James Appathurai told reporters during the Bucharest summit.
Among those considerations, of course, is a reluctance on the part of some members -- most notably Germany and France -- to antagonize Russia, which staunchly opposes Georgia and Ukraine's efforts to join the Western alliance.
But analysts say it isn't just Russian opposition that is keeping the two former Soviet republics' NATO dreams on hold. Although both countries have made impressive progress on military and political reform, both also still have significant issues that need to be resolved.
Analysts say Georgia also needs to complete critical political reforms and must make progress in resolving conflicts in the separatist regions of Abkhazia and South Ossetia, which are strongly supported by Moscow.
For its part, Ukraine needs to overcome deep divisions in both the public and the political elite over joining NATO, and fully bring its armed forces under civilian control.
'A Political Army'
NATO officials say Ukraine has made great strides in bringing its military in line with the alliance's standards. Concerns remain, however, regarding the country's Interior Ministry troops, which are highly politicized and slow to reform.
"These is a problem with civilian control over the armed forces," says Eugeniusz Smolar of the Warsaw-based Center for International Relations explains. "In Ukraine there is a so-called Interior Army, which is unacceptable from the point of view of NATO standards. It is subjugated to the minister of the interior. This is a problem. This is a sort of political army, which we can't have. So they have a job to do."
Yushchenko has tried, thus far unsuccessfully, to reform the Interior Ministry troops. On April 8, for example, parliament rejected a bill that would have turned the Interior Ministry troops into a Ukrainian National Guard directly subordinate to the president.
The Ukrainian president is also trying to convince a skeptical public that joining NATO is a good idea. According to recent polls, just one in four Ukrainians supports joining the military alliance, and the political elite remains deeply divided as well.
Yushchenko's pro-Moscow political opponent, Viktor Yanukovych, and his Party of Regions staunchly oppose joining NATO. And even Yushchenko's Orange Revolution ally, Prime Minister Yulia Tymoshenko, while generally supportive, has been reluctant to embrace the goal as enthusiastically as the president would like.
The issue promises to be hotly contested in Ukraine's 2010 presidential election. Yanukovych is widely expected to challenge Yushchenko in that race and Tymoshenko is also believed to be considering a run.
Yushchenko this week announced that Ukraine would hold a referendum on NATO membership in two years' time.
Tbilisi's Political Challenges
Georgia also has some work to do before its bid for a MAP is considered at NATO's foreign ministers' meeting in December.
"If you look at the Riga summit declaration, the NATO countries encouraged Georgia to continue making progress on political, economic, and military reform," says Koba Liklikadze, a military affairs correspondent with RFE/RL's Georgian Service, referring to the declaration from the November 2006 summit in the Latvian capital. "This includes strengthening judicial reform and a peaceful -- and I want to underline peaceful -- resolution of outstanding conflicts on its territory."
Most Western analysts say Georgia has made significant progress in bringing its military in line with NATO standards. Its forces are under civilian control and its troops are increasingly well-trained and equipped.
But Tbilisi still has some gaps to fill in its political reforms. Most notably, analysts say Georgia needs to reform its highly politicized judicial system.
Moreover, Georgia's reputation as a beacon of democratic reform in a largely authoritarian South Caucus region suffered a severe blow in November when President Mikheil Saakashvili temporarily declared emergency rule following opposition street protests.
Georgian officials have long argued that NATO membership would help to deepen democracy and prevent backsliding on the progress made thus far. But some analysts say such a strategy -- reportedly employed by Saakashvili in Bucharest -- could prove counterproductive.
"If the quality and strength of Georgian democracy depends on NATO, that means that NATO will hesitate before it will accept you among us," Smolar says.
Saakashvili says he is aware of Western concerns about the permanence of Georgia's reforms, and that parliamentary elections scheduled for May 21 will be a critical test of his country's democratic mettle. He even proposed inserting language in the Bucharest summit's final communique to allay fears that Tbilisi is backsliding on democratic reform.
"It was our initiative to include into the communique the phrase about the necessity to conduct fair and clean elections," Saakashvili said in a recent interview with Georgia's Rustavi-2 television. "It was our proposal, which is [an effort] to show once again that Georgia has truly taken the path to democracy."
Saakashvili is also aware that he needs to show progress in resolving the so-called frozen conflicts in breakaway Abkhazia and South Ossetia. On March 28, the Georgian president unveiled a peace plan that would offer Abkhazia broad autonomy, a joint free-trade zone, and a vice president who would have veto power over decisions related to the province.
Abkhaz officials have rejected the proposal.
In a recent interview with RFE/RL, Georgian Reintegration Minister Temur Iakobashvili said Georgia's frozen conflicts will not be resolved until Russia shows a willingness to negotiate in good faith.
"The peace process has not started, because there is one country, called Russia, which does not want this process to start, and wants to continue the status quo," Iakobashvili says. "The only way to make Russia more amenable toward the peace process is for Georgia to enter NATO. This would end all talk about separatism, and since entering NATO is a process, we think that as soon as this process becomes irreversible, Russia will come to the negotiating table, so that the peace process will start and move on."
While Georgia and Ukraine are hoping they will finally get their MAPs in December, most analysts say the eight months between now and then is insufficient to satisfactorily address the issues on the table.
Smolar, for one, says the earliest realistic date will be NATO's 2009 summit in the eastern French city of Strasbourg and its German border town, Kehl.
"I expect this to happen at the 60th anniversary of NATO, if everything goes well. If Ukraine and Georgia do their homework," Smolar says.
RFE/RL's Georgian and Ukrainian services contributed to this report
Where They Stood
Which NATO members stood where over Ukrainian and Georgian Membership Action Plans, denied to the two countries, at least temporarily, by the NATO leaders at their Bucharest summit? The stances of most allies appear to have been determined by how they see the role of the United States in NATO and what their views are of Russia.
United States -- NATO's linchpin. Firm supporter of MAPs, and NATO (and, somewhat controversially, EU) enlargement to Europe's new democracies. Actively seeks to check Russia's resurgence, believes Europe does too little to secure itself against Moscow.
United Kingdom -- A very close ally of the United States. The EU suspects Britain's "special relationship" with Washington to rival its commitment to Brussels. Relations with Russia hit rock bottom in the aftermath of the poisoning of Aleksandr Litvinenko.
Canada -- A very close ally of the United States. Firm supporter of MAPs and NATO enlargement.
Denmark -- A staunch Atlanticist. Often an outspoken critic of Russia, but pacifist leanings tend to marginalize it in debates over European defense.
Iceland -- Close U.S. ally.
Poland -- The largest "new" ally, aspires to set the tone for all ex-communist NATO member states. A loyal U.S. ally, but with an independent streak (bargains hard over missile-shield site). Sees Russia as its main strategic threat, but also views Germany with distrust.
Czech Republic -- Staunch Atlanticist, a very close U.S. ally. Critical of Russia.
Slovakia -- Close U.S. ally. Prizes close relations with neighbor Ukraine. Subject to some Russian "pan-Slavic" lobbying.
Slovenia -- Close U.S. ally. Less concerned about Russia than other Eastern European countries. Susceptible to "pan-Slavic" lobbying by Russia.
The Baltic countries -- Estonia, Latvia and Lithuania are very close U.S. allies. Their relations with Russia are fraught and all want to roll back Moscow's influence over its ex-USSR neighbors.
Romania -- Close U.S. ally. Traditionally distrustful of Russia.
Bulgaria -- Close U.S. ally. However, feels a burden of gratitude toward Russia for help given against Ottoman Turkey in the 19th century. Appears susceptible to Russian economic (as with the recent Gazprom deal on the Blue Stream pipeline) and "pan-Slavic" lobbying.
Turkey -- Close U.S. ally, though differences exist (notably over Iraq). Supports NATO enlargement, but believes Russian concerns must be addressed. Supported MAPs for Ukraine and Georgia, but indicated it would fall in line with the consensus view.
Germany -- NATO's largest European ally, largest EU member state. Increasingly vocal on European security. Dependence, economic or otherwise, on Russia is overstated, as is antagonism with Washington. Proceeds from the deeper strategic calculation that relentless global setbacks risk pushing Russia into isolation, thus jeopardizing the stability of the continent.
France -- United States' main detractor in NATO (left NATO's military structures in 1966). Seeking to reassert itself globally. Given to a certain opportunism, especially vis-a-vis Russia. Also views itself as being in a tacit competition with Germany for influence in Europe. Has come to view further eastward expansion of both NATO and the EU as an anathema.
Italy -- Generally follows the Franco-German lead (all thee are among the EU's founder nations). Traditionally friendly toward Russia. Right-wing governments tend to be more pro-U.S. in their preferences than the general public.
Spain -- See Italy.
Portugal -- See Spain.
Greece -- General public very averse to the United States. As an Orthodox nation, feels a special affinity to Russia.
Belgium -- An EU founder nation, tends to follow the Franco-German lead.
Luxembourg -- See Belgium.
The Netherlands -- Traditionally a staunch Atlanticist/close U.S. ally. An EU founder nation. Appears to subscribe to the German school of thought on Russia. Famously skeptical of further EU enlargement.
Hungary -- The only ex-communist ally failing to sign a letter in support of MAPs for Ukraine and Georgia. Left-wing governments (current and previous) tend toward a friendlier view of Russia than is the norm in Eastern Europe. Susceptible to Russian economic lobbying (again, note the recent Gazprom deal on Blue Stream).
Norway -- Usually close to the United States and Britain in its views. Non-EU member.
By RFE/RL Brussels correspondent Ahto Lobjakas