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."
Georgia is said to have made great progress in bringing troops into line with NATO standards (AFP)