From the NY Times

NATO Ships in Black Sea Raise Alarms in Russia
By ANDREW E. KRAMER
Published: August 27, 2008
MOSCOW — Russian commanders said Wednesday that they were growing alarmed at the number of NATO warships sailing into the Black Sea, saying that NATO vessels now outnumbered the ships in their fleet anchored off the western coast of Georgia.

As attention turned to the balance of naval power in the sea, the leader of the separatist region of Abkhazia said he would invite Russia to establish a naval base at Sukhumi, a deep-water port in the territory.

But in a move certain to anger Russia, Ukraine’s president, Viktor A. Yushchenko, said he would open negotiations with Moscow on raising the rent on the Russian naval base at Sevastopol, which is in Crimea, a predominantly Russian province of Ukraine. ....
...
In Moscow, the naval maneuvering was clearly raising alarms. Russian commanders said the buildup of NATO vessels in the Black Sea violated a 1936 treaty, the Montreux Convention, which they maintain limits to three weeks the time noncoastal countries can sail military vessels on the sea.

Col. Gen. Anatoly Nogovitsyn, the deputy chief of the Russian General Staff, said at a briefing in Moscow that under the agreement, Turkey, which controls the straits of the Bosporus and the Dardanelles, must be notified 15 days before military ships sail into the sea, and that warships could not remain longer than 21 days.
http://www.nytimes.com/2008/08/28/wo...in&oref=slogin

The legal squabble here involves the 1936 Montreux Convention.

The Montreux Convention Regarding the Regime of the Straits was a 1936 agreement that gives Turkey control over the Bosporus Straits and the Dardanelles and regulates military activity in the region. Signed on 20 July 1936, it permitted Turkey to remilitarise the Straits and imposed new restrictions on the passage of combatant vessels. It is still in force today, with some amendments.

The Convention gives Turkey full control over the Straits and guarantees the free passage of civilian vessels in peacetime. It severely restricts the passage of non-Turkish military vessels and prohibits some types of warships, such as aircraft carriers, from passing through the Straits. The terms of the convention have been the source of controversy over the years, most notably concerning the Soviet Union's military access to the Mediterranean Sea. ....
http://en.wikipedia.org/wiki/Montreu...urkish_Straits

This rather archaic convention has more holes in it than Ankara cheese. So, it is something that both sides can squawk about. The US is not a signatory; but, in the view of the USN, is indirectly bound:

Turkey is a NATO partner, and the United States is obligated to take no action that would undermine Turkey's authority to control transit through or over the Straits, as provided for in the Montreux Convention.
http://www.ntip.navy.mil/montreux_convention.shtml

And, from the same source:

Warships of non-Black Sea powers may not remain in the Black Sea longer than 21 days.
So, Nogovitsyn seems to be correct on the 21 day limit - not much time to mount an offensive operation - which seems the point of the convention.