EBay is asking all of its users to change their passwords, following a recently discovered data breach from late February. Apparently employee login credentials were compromised, allowing intruders to access a database containing eBay customers’ name, encrypted password, email address, physical address, phone number and date of birth. However, the database did not contain financial information or other confidential personal information. Unfortunately, data breach announcements throw around the term "encrypted password" loosely, so we don't know if they are encrypted (meaning they can be decrypted with a key, not a best practice), or hashed (meaning they cannot be decrypted, which is good). In either case, there are bigger risks associated with the breach of personal data that could be used to aid identity theft.
If you are an EBay user, change your password. If that password was used on other accounts, change those too, to something different. While there was no breach at PayPal, it wouldn't hurt to change that one too, and make it different from your EBay password.
Please note that both EBay and PayPal support two-factor authentication with the PayPal Security Key. I highly recommend that you get one and use it on both accounts. Note that one of the options is the Symantec VIP soft token, which runs on your smartphone. You don't need to put another token on your keyring to add this extra security.