The email titled "Reminder: Important changes to PayPal Accounts in the European Union" is NOT a Phishing email
The reason for this post is to make sure that those who subscribe to my blog and saw my earlier inaccurate post will see the correction and also to give this message the same profile. I have edited the original post.
Thanks to Rab for investigating and finding out that the email titled "Reminder: Important changes to PayPal Accounts in the European Union" did indeed come from Paypal and wasn't a Phishing email as I'd incorrectly stated.
Rab sent a copy of the message he received titled "Reminder: Important changes to PayPal Accounts in the European Union" to spoof@paypal.com who verified that it was a valid email that they'd authored.
I have not been contacted by Paypal and have posted this purely to correct my earlier statement and to apologise to anyone including Paypal who may have been inconvenienced by my inaccurate post. Paypal provide excellent resources detailing how to detect Phishing emails including their Phishing Guide.