Using 'AsParallel()' / 'Parallel.ForEach()' guidelines?

Several points.

writing just countriesAndAliases.AsParallel() is useless. AsParallel() makes part of Linq query that comes after it execute in parallel. Part is empty, so no use at all.

generally you should repace foreach with Parallel.ForEach(). But beware of not thread safe code! You have it. You can't just wrap it into foreach because List<T>.Add is not thread safe itself.

so you should do like this (sorry, i didn't test, but it compiles):

        return countriesAndAliases
            .AsParallel()
            .SelectMany(s => 
                IsCountryNotAlias(s)
                    ? Enumerable.Repeat(s,1)
                    : AliasCountryLists[s]
                ).Distinct();

Edit:

You must be sure about two more things:

1. IsCountryNotAlias must be thread safe. It would be even better if it is pure function.
2. No one will modify AliasCountryLists in a meanwhile, because dictionaries are not thread safe. Or use ConcurrentDictionary to be sure.

Useful links that will help you:

Patterns for Parallel Programming: Understanding and Applying Parallel Patterns with the .NET Framework 4

Parallel Programming in .NET 4 Coding Guidelines

When Should I Use Parallel.ForEach? When Should I Use PLINQ?

PS: As you see new parallel features are not as obvious as they look (and feel).

When using AsParallel(), you need to make sure that your body is thread safe. Unfortunately, the above code will not work. List<T> is not thread safe, so your addition of AsParallel() will cause a race condition.

If, however, you switch your collections to using a collection in System.Collections.Concurrent, such as ConcurrentBag<T>, the above code will most likely work.