A new paper just published in the Geophysical Review Letters finds a significant correlation between the Atlantic Multidecadal Oscillation (AMO) and the water temperature of the Barents Sea.
This was made possible by a significant network of hydrographical stations in the Barents Sea which resulted in a 230,000 temperature profiles used in this analysis. The hint in the conclusion (which the authors stop short of defining) is that the pattern of data, seen below, might be linked to the recent pattern of Arctic sea ice melt and some partial recovery seen in the last two years. Their figure 2 below, certainly seems to suggest a strong correlation between water temperature in the Barents Sea and the AMO index.
The paper is:
Levitus, S., G. Matishov, D. Seidov, and I. Smolyar (2009), Barents Sea multidecadal variability, Geophys. Res. Lett., 36, L19604, doi:10.1029/2009GL039847.
We present area-averaged time series of temperature for the 100–150 m depth layer of the Barents Sea from 1900 through 2006. This record is dominated by multidecadal variability on the order of 4C which is correlated with the Atlantic Multidecadal Oscillation Index.
The thermohaline regime of the Arctic Ocean is determined by several key processes—the inflow of Atlantic Water (AW) through two gateways—the Fram Strait [Schauer et al., 2004; Walczowski and Piechura, 2006] and the Barents Sea (BS) [Furevik, 2001], air-sea interaction in the Arctic, river runoff [Peterson et al., 2002], and Pacific water inflow through the Bering Strait [Jones et al., 2008; Woodgate and Aagaard, 2005; Woodgate et al., 2006]. If the BS, as one of the gateways to the Arctic, is warming, there is a possibility that this warming may be amplified in the Siberian Arctic Seas due to reduced seasonal sea ice cover resulting from the ice-albedo feedback effect. Temperaturesalinity anomalies of the water comprising the boundary currents of the Arctic may propagate towards the interior of the Arctic as thermohaline intrusions [Carmack et al., 1997; McLaughlin et al., 2009]. Recent analyses emphasize strong interannual to decadal variability of the Arctic Ocean [e.g., Dmitrenko et al., 2008a, 2008b; Polyakov et al., 2008] that depend or may depend on the interplay of the above mentioned climatic elements. Alekseev et al.  provide a detailed review of Arctic Ocean variability.  Observations and climate models suggest that certain teleconnections and feedbacks link interannual to decadal variability between the Arctic Ocean and other geographic regions. The most prominent feedbacks identified so far are the linkages between Arctic climate variability and the North Atlantic Oscillation (NAO)/Arctic Oscillation (AO). Both the NAO and AO are characterized by vacillations of the atmospheric pressure systems of mid-latitude highs and high-latitude lows, with the ocean-atmosphere interactions in the northern North Atlantic being the lead factor in the NAO [Visbeck et al., 2001]. There is evidence of links between the NAO and the circulation patterns of the Arctic Ocean characterized by multidecadal oscillations with periods of 10 to 40–60 years [Mysak, 2001]. A discussion of the robustness of correlations between the NAO and other effects with BS climate dynamics was given by Goosse and Holland . Using the Community Climate System Model, version 2 (CCSM-2), they found a persistent correlation between the thermal history of the model BS and the history of model AW inflow. Their model runs showed that variability in air-sea exchange and heat transport in the BS dominate in forcing Arctic surface air temperature variability suggesting an important role of the BS in Arctic climate dynamics. In addition to the recent multidecadal decrease in the extent of Arctic sea ice cover there has been a dramatic drop during 2007. This sudden decrease does not appear to be directly related to the NAO or AO [Zhang et al., 2008; Overland et al., 2008]. 
The BS is perhaps the only Arctic sea where presently available in situ observations are sufficient for unambiguous detection and analysis of long-term ocean climate variability. Because it remains ice-free almost throughout the year, the BS is covered by a well-developed observational network of standard sections [Matishov et al., 1998] (Figure 1a) accompanied by a large number of historical and recent ocean profiles that are not part of this network (Figure 1b) that are available in the World Ocean Database (WOD) [Boyer et al., 2006] (data available at http://www.nodc.noaa.gov). The BS serves as a transit zone between the upper layer warm water masses of the Atlantic Ocean and cold waters of the Eastern and inner Arctic. Therefore ocean conditions and long-term climatic trends in the BS may be indicative of the overall climate change in the Arctic Ocean, or at least in its eastern half. Our goal is to document the long-term thermohaline history of the BS that may be important for better understanding and prediction of possible changes in the Arctic Ocean.
Average BS temperature trends in the 100–150 layer agree with previous findings that the Arctic has warmed during the past 30 years. These trends align closely with spectacular surface air temperature increase over the entire Arctic and with the rapid sea ice retreat [Arguez et al., 2007]) since the end of the 1990s. Since the late 1970s the temperature of the 100–150 m layer of the BS increased by
approximately 4°C as part of multidecadal variability that is correlated with the AMO Index for the past 100 years.  However, despite good qualitative agreement between the BS oceanic climate trends and other climate tendencies in the Arctic, we must draw attention to some caveats inherent to our work. First, there is some uncertainty in ‘‘connecting the dots’’ between a warmer BS and reduced sea ice cover in the central Arctic—the presumed link between the two observables, which is yet to be explained. One of the plausible explanations would be to link AW throughflow in the BS to a lower rate of seasonal sea ice growth in winter in the BS [Wu et al., 2004] and further downstream of the throughflow. However, AW sinks and thus may not have that much impact downstream on ice cover. Recent results suggest that the advection of warming near-surface water from the North Pacific Ocean to the Arctic Ocean through the Bering Strait may play a significant role in Arctic sea-ice retreat [Woodgate et al., 2006]. Thermohaline intrusions of relatively warm water from the Arctic boundary currents into the Arctic interior [McLaughlin et al., 2009] may play a role. Aerosols may also play a role [Shindell, 2007].  Prior to about 1970, there was generally above average sea ice cover, with the maximum extent observed in the late 1960s. Since the late 1970s sea ice extent has decreased substantially [Comiso et al., 2008], whereas, simultaneously, AW has become warmer and perhaps more abundant in the BS. The warmer air and the gradual decrease of albedo of thinning ice in summer would cause melting from above. Additionally, the sea ice decrease may be due to heating from below, when the water mixing channels heat stored in subsurface layers toward the sea ice base. More and warmer AW may contribute to shortening or complete elimination of seasonal sea ice presence in some part of central and eastern Arctic. It is still not clear whether, or how much, subsurface AW has directly contributed to the substantial ice melting that has been observed during last 20 years in the central Arctic; another plausible explanation for an AW role in this process may be the BS impact on the Arctic climate via ocean-air interaction [Goosse and Holland, 2005]. (See also the comment on possible role of Bering Straight inflow above.)
Leif Svalgaard was kind enough to alert me to this paper, and he has a copy available for viewing here (PDF)