The two leaders, holding their first face-to-face meeting since Medvedev took the reins from Vladimir Putin in May, also highlighted their cooperation in diplomatic efforts to resolve nuclear disputes with Iran and North Korea.
"There are topics on which we are making progress, such as Iran and North Korea, but there topics on which we diverge, such as the missile shield and European matters, but there are possibilities for agreement," said Medvedev at the meeting on the fringes of a summit of rich nations in Japan.
"While there's some areas of disagreement, there's also areas where I know we can work together for the common good," said the US president. "I found him to be a smart guy who understood the issues very well."
"Iran is an area where Russia and the United States have worked closely in the past and will continue to work closely to convince the regime to give up its desire to enrich uranium," he added.
Seven years after Bush declared he had looked into Putin's eyes at their first meeting, seen his soul, and deemed him trustworthy, the US president declined to offer a similar assessment of the new Russian leader.
"I'm not going to sit here and psychoanalyse the man, but I will tell you that he's very comfortable, he's confident," said Bush. "You may not agree with what he tells you, but at least you know it's what he believes."
Later, Medvedev's diplomatic adviser, Sergei Prikhodko, said the Russian president had warned Bush that installing part of a missile defence shield in Lithuania was "absolutely unacceptable."
Thus-far inconclusive US talks with Poland on basing 10 missile interceptors there have fuelled media reports that Washington may be looking at other possible sites, including Lithuania.
"Any missile defence installation, no matter where in Europe, is not a threat to Russia," said White House spokesman Gordon Johndroe, who called any discussion of bases in Lithuania rather than Poland "premature."
Bush leaves office in fewer than 200 days and is here at his last Group of Eight (G8) summit, while Medvedev took office in May and is making his debut at the elite gathering of leaders of wealthy nations.
"I reminded him that, yes, I'm leaving, but not until six months and I'm sprinting to the finish. So we can get a lot done together and, you know, a lot of important issues," said the US leader.
Bush had been expected to raise US worries about the rule of law and democracy in Russia, and flaring tensions between former Soviet satellite Georgia and its giant neighbour are on the agenda, US officials said.
He had also planned to reaffirm his support for admitting Russia to the World Trade Organisation as they met on the margins of the Group of Eight (G8) summit of industrialised nations in his mountain resort.
With his youthful image and reputation for openness, Medvedev, 42, cuts a different character than his mentor Putin, who retains the powerful post of prime minister.
In policy terms, Medvedev has few differences from Putin -- notably opposition to US plans to deploy a missile defence system against what Washington says is a threat from Iran and North Korea.
US Secretary of State Condoleezza Rice is due next week in the Czech Republic to sign a deal to deploy an anti-missile radar, and may stop in nearby Poland to sign a pact to base 10 missile interceptors there, US officials say.
The United States wants to deploy the shield in the central European nations by 2011-2013 amid concerns about the impact on ties with Russia, which denounces the plan as a threat to its own security.
© 2008 Agence France Presse