SQL Server 2012 :: Significant Performance Dropping When Use CASE Statement

1. I have a simple JOIN statement between A and B, e.g. Cities A JOIN Countries B:

SELECT A.City_Name, B.Country_Code, B.Country_Area
FROM Cities A
JOIN Countries B
ON B.Country_Id = A.Country_Id
WHERE B.Country_Type='ABC';

That statement works absolutely fine, very fast (less than a second) and returns me 2 records

2. I need to replace Country Area column with 1 for Europe and 0 for all the rest. I implement so in the following way:

SELECT A.City_Name, B.Country_Code, CASE B.Country_Area WHEN 'EUR' THEN 1 ELSE 0 AS Country_Area
FROM Cities A
JOIN Countries B
ON B.Country_Id = A.Country_Id
WHERE B.Country_Type='ABC';

Now to get the same two records it takes 03:55 minutes (!)

I have looked into Estimated Execution Plan, but couldn't spot any difference - all straight forward.

It is SQL 2012 SP1 with compatibility level set to 110