Medvedev told reporters in the German capital on his first visit to western Europe since succeeding Vladimir Putin as head of state last month that several disputes were driving a wedge between Russia and the West.
"Tendencies towards a weakening of mutual understanding worry us ... first and foremost in questions of global and European security, including on US missile shield plans in Europe, the CFE (Treaty on Conventional Armed Forces in Europe), NATO enlargement," he said.
Moscow froze the CFE treaty - which sets limits on troops and military hardware across the continent - in December and is locked in a standoff with Washington over US plans for a missile defence shield in eastern Europe.
Medvedev added after talks with German Chancellor Angela Merkel that the West had no business meddling in Russian affairs such as the high-profile case of jailed Kremlin critic and former oil tycoon Mikhail Khodorkovsky.
"Issues related to the serving of sentences should not become the subject of inter-state negotiations," he said.
A lawyer for Khodorkovsky, Yury Schmidt, told AFP Thursday he was more hopeful for his client's release following talks he held with German Foreign Minister Frank-Walter Steinmeier during a visit to Russia in mid-May. He called on Berlin to raise the issue during Medvedev's stay.
Formerly Russia's richest man and chief executive of oil giant Yukos, Khodorkovsky has been in prison in Siberia since May 2005 after being convicted under Putin for fraud and tax evasion. His imprisonment and the subsequent break-up and state takeover of Yukos shocked Western politicians, rights groups and companies worried about the rule of law in Russia.
The president's one-day visit to Germany came as Russian authorities summoned the head of British-Russian energy company TNK-BP for questioning as part of a tax probe, amid a battle for control of the firm.
Despite the uncompromising tone, Medvedev said booming trade would be a catalyst for improving relations.
And Merkel expressed hope that a new EU-Russia partnership agreement to be wrapped up quickly after negotiations resume at a long-delayed at a summit in Siberia later this month, with energy ties topping the agenda as the EU grows increasingly reliant on Russian oil and gas.
A Kremlin source had said earlier that Medvedev would seek common ground with Germany on issues including the expansion of NATO to Russia's borders, the status of Kosovo and Iran's nuclear programme.
"In light of the growing negative trends in international affairs, frank dialogue between Russia and Germany is very useful and will continue on a wide spectrum of subjects," the source said.
"The two countries' common interests are much greater than their differences. The unique nature of the Russian-German relationship has the capacity to find a compromise and surmount the problems that arise."
Meanwhile Berlin was keen to develop a clearer picture of the new head of state including the extent of his power with Putin now serving as prime minister.
There was friction between Merkel, a fluent Russian speaker who grew up in communist East Germany, and Putin, a former KGB agent in Dresden, due to her outspoken criticism of alleged human rights violations and growing authoritarianism in Russia.
A week after his May 7 inauguration, Medvedev had underlined the importance of a strategic partnership between Germany - Europe's biggest economy - and Russia when he announced the trip to Berlin.
Merkel last week urged greater cooperation between NATO and Russia, citing the conflict over US plans for the missile defence shield as just one area where dialogue as needed.
Warsaw moved to accommodate Moscow's concerns over the issue Thursday by saying that it would be willing to give Russian inspectors access to any facility built on Polish soil.