It doesn't matter which colors you use, as long as they are all different. So, yes, it would work for 4 different shades of pink because they are all different. It would also work for four shades of blue, green, maybe two of red and two of grey, etc.

Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded. Notice in jfribrg's diagram, the brown country is completely surrounded. Go ahead and try it yourself on a piece of paper.

There is, however, an unstated premise: All the countries have to be in one piece. For example, the United States is not in one piece because of Alaska. There are two large "pieces" of the U.S. (and various islands)... If you tried this on the actual map of the Earth, you might not find the 4 color theorem is true (then again, it might be. I've never tried it).

__________________
"Critical thinking and skepticism form the cornerstone of intelligence."
-me