MOSCOW---To commemorate the 65th anniversary of the defeat of Nazi Germany, Russia staged an impressive Victory Day celebration on May 9, with plenty of troops and military hardware rolling through Red Square and a display of air power in the sky above Moscow. On first glance, it was just like the good old (or bad old) days.

But among those troops on parade were U.S. and British soldiers. Joseph Stalin’s picture was banned from the many posters in the center of the city, and Lenin’s Tomb – the reviewing stand for so many Cold War ceremonies – was covered by a billboard.

So, is this finally the new Russia, reaching out without the defensiveness that has so long characterized its attitude toward the rest of world? Particularly with regard to the United States, the answer is “No.”

The problem is not a Cold War hangover, but rather a series of more recent American actions. The bombing of Belgrade in 1999, NATO’s expansion, and President George W. Bush’s plan to establish an anti-missile defense system based in Poland and the Czech Republic are among the reasons for what Russian foreign policy experts and American diplomats here cite as pervasive anti-Americanism.

President Obama has rolled back the missile-defense plan and shows little interest in adding more former Soviet-bloc states to NATO. But an “Obama bounce” in opinion about the United States is hard to find here. In a survey conducted last August, respondents named the United States as Russia’s principal enemy, followed by Chechen separatists. In a more recent poll, a solid majority of respondents picked the United States as “the biggest threat to Russia’s national security,” with North Korea and Iran trailing far behind.

The United States Embassy in Moscow is well equipped to respond to this. Ambassador John Beyrle is fluent in Russian (he writes a Russian-language blog) and is highly visible. He recently opened an exhibit paying tribute to his father, a U.S. serviceman who was captured by the Germans during the Normandy invasion in 1944, escaped from his POW camp, and joined Russian forces as they fought their way toward Berlin. In addition to the ambassador’s efforts, the embassy staff works hard on exchange programs and other useful projects.

Lacking, however, is support from Washington in the form of a carefully thought-out and articulated U.S. public diplomacy policy toward Russia. With so much emphasis on public diplomacy toward the Arab world, crucial matters such as improving relations with Russia get too little attention. Needed is a coherent, cohesive public diplomacy strategy for Russia, endorsed by the White House and State Department, as the foundation on which American diplomats in Russia can build.

In my conversations with Russian international relations experts, I asked: “Doesn’t Russia consider Iran a threat?” “Yes.” “Isn’t China seen as a serious competitor?” “Yes.” “Well, then, is there not common ground for a new U.S.-Russia détente?” “Yes, but….”

The “but” comes from an unspecific but entrenched feeling that the United States treats Russia today as a second-rate power. The days when the Soviet Union, along with the United States, dominated global politics are not yet so distant that they have lost their resonance. Virtually everyone I spoke with talked about anti-Americanism among older people who remember the Cold War and, more disturbingly, among younger people with limited education – a huge number – whose nationalism flares when ignited by perceived U.S. insults.

Responding to this is not so different from meeting challenges facing U.S. public diplomacy elsewhere in the world. Wherever these challenges arise, they must be met by a sophisticated and comprehensive public diplomacy strategy. Until that is created, U.S.-Russian relations will only get worse.