Sì, probabilmente è un brutto segno.
Prima di tutto, però: questa potrebbe essere semplicemente una mail di phishing che spera di fare clic su qualche link nella mail che dice "segnala un problema con questa email a Paypal", ma ti porta in un sito diverso dal vero sito paypal e ti consente di inserire le tue credenziali lì. Quindi, la cosa peggiore che puoi fare è cliccare su qualsiasi link da questa mail. Puoi controllare il vero obiettivo dei link - se non sono su server che sono inequivocabilmente paypal.com, allora puoi essere abbastanza sicuro che questo non è altro che un tentativo di phishing.
Vai al link (magari usando un'altra macchina diversa da quella che usi normalmente per inserire le tue credenziali Paypal, dal momento che hai ragione di presumiamo che sia stato compromesso), controlla il certificato di quel sito Web e ottieni un numero di telefono da chiamare. Cambia la tua password Paypal da una macchina che si può ragionevolmente ritenere sia priva di malware che potrebbe provare a rubare le tue credenziali.