What does each measure?
Pearson's correlation coefficient is measure of the strength of a linear relationship between x and y. It is swayed by outliers much like a mean and standard deviation.
Spearman's correlation coefficient is a measure of the strength of a monotonic relationship between x and y. This includes but is more general than just linear relationships, including all one-to-many relationships, but does not include many-to-one or many-to-many relationships. It is robust against outliers much like a median and inter-quartile range.
Mutual Information is a general measure of the strength of all of these types of relationship, and tends to work best with less noisy data.
Hauke et. al.
In the case of the paper you refer to, in their graph of X12 (birth rate) vs X7 (population of working age), some outliers prevent the Pearson's correlation from agreeing with the Spearman's correlation for the same data. This is because the Spearman's correlation coefficient, as a rank measure, is robust against a few outliers much like a median is robust to outliers. In regards to their data, I'm not sure what strange normalisation they have performed to get a birth rate of -6000! 
In the case of X4 (Population density) vs. X5 (Arable land), we have a non-linear, non-monotonic relationship. There are four data points at high population density (in a city) and for these, roughly the higher the density, the less space for farms, so we have a negative correlation. Down with most of the data in the low population density regions, in less hospitable regions (mountains, deserts, etc) there are less people and less farms, and in the more lush regions there are more people and more farms, so we have a positive correlation.

So I would replace their conclusion with
Always plot your data
Understand the actual meaning of the numbers
Understand what each correlation measure can tell you about your data (as above)