Why is Europe warmer than North America at similar latitudes?
It is true that the Gulf Stream plays a role on the different climates of each region; I would not call it an 'urban legend' as Richard Seager and other scientists put it, however it seems that how much it actually changes the climate is currently under debate.
From Wallace Broeker:

One of the major elements of today's ocean system is a conveyor-like circulation that delivers an enormous amount of tropical heat to the northern Atlantic. During winter, this heat is released to the overlying eastward air masses, thereby greatly ameliorating winter temperatures in northern Europe.



Thermohaline circulation—often dubbed &quot;the ocean conveyor belt&quot;—carries warm surface waters (pink) from the tropics to the North Atlantic, with the return flow at depth (purple). But contrary to many accounts (summarized by diagrams such as this), this heat conveyor plays only a minor role in keeping European countries warm during winter months.

It seems that although, as you stated, the Gulf Stream traditionally was thought to play a major role in the climate difference, new studies emerging shows that only contributes a small amount to the temperature difference.

The cooling effect could account for 30 to 50 percent of the temperature difference across oceans, the study suggests.  It also explains why the cold region is just as big for both North America and Asia, despite the continents' differences in topography and size.
The cooling depends on heating air over warm ocean water. Since the warm currents along western ocean boundaries in both the Pacific and Atlantic are similar, the resulting cold region to their west would be similar as well.  The new study adds to other recent research that found that ocean currents such as the Gulf Stream aren't capable of transporting that much heat to northern Europe, instead contributing only up to 10 percent of their warming.

There are also studies suggesting that the conveyor belt model itself was extremely oversimplified, and its role in ocean overturning cycles is being re-evaluated:

As the study of the modern ocean’s role in climate continues apace, the conveyor belt model no longer serves the community well — not because it is a gross oversimplification but because it ignores crucial structure and mechanics of the ocean’s intricate global overturning.

Based on the evidence at hand, I believe that the Gulf Stream does play a role in making Europe warmer than North America at similar latitudes; however how large a role it plays perhaps has been overestimated, and with the new ongoing studies perhaps different climate elements, such as the atmospheric elementsrather than the oceanic currents, can be modeled and brought to light in the scientific community, much as Richard Seager is doing now.

The oceans do still play an important role in keeping Europe’s winters mild, but it is nothing to do with the Gulf Stream. The winds that blow northeast onto Europe from the Atlantic carry with them air that is relatively warm even in the winter; the large heat capacity of water means that the sea cools off more slowly in the winter, and this also moderates the temperature of the air above the sea surface. This contrasts with the eastern US, where the prevailing southeast winds are cold, having lost their heat to the thousands of kilometres of land surface they’ve already passed over.
So the oceans are still involved, but it is the atmosphere that is the true key to explaining Europe’s mild winters; and in a pleasing geological twist, it is apparently the presence of the Rocky Mountains that causes the large scale waviness of atmospheric circulation that magnifies the temperature contrasts on either side of The Pond (Richard Seager explains this in more detail in this more comprehensive piece at the American Scientist).