Sí, esto es probablemente una mala señal.
En primer lugar, sin embargo: esto podría ser simplemente un correo de suplantación de identidad que espera que haga clic en algún enlace del correo que diga "informar un problema con este correo electrónico a Paypal", pero lo lleve a un sitio web diferente al del sitio real de PayPal y le permite introducir sus credenciales allí. Entonces, lo peor que puedes hacer es hacer clic en cualquier enlace de este correo. Puede verificar el objetivo real de los enlaces: si no están en servidores que son inequívocamente paypal.com, entonces puede estar bastante seguro de que esto no es más que un intento de phish.
Vaya a enlace (tal vez use una máquina diferente a la que normalmente usa para ingresar sus credenciales de Paypal, ya que tiene motivos para suponga que se ha comprometido), verifique el certificado de ese sitio web que le parece correcto y busque un número de teléfono de contacto para llamar. Cambie su contraseña de Paypal desde una máquina que pueda asumir razonablemente que está libre de malware que podría intentar robar sus credenciales.