It really doesn't matter what flavor of Linux you're using.

Do you actually have a cert and a private key, and did you import your cert (and private key) into Thunderbird's certificate store?

Yes, I did, I installed Thunderbird and by doing so, I got a new key, but I also installed my old key and the keys I have from people I know. Could these two keys I have now create problems? I didn't know how to avoid creating a new one. I found out right now that I can sign and encrypt mails with very few people, but in most cases I get the error message...

I installed Thunderbird and by doing so, I got a new key

You certainly don't get a new key by just installing Thunderbird. You do need a CA (Certificate Authority) to issue a new cert for your email address.

I also installed my old key and the keys I have from people I know.

It would probably be a good idea if you explain in more detail what exactly you did. Screenshots will help. https://support.mozilla.org/kb/how-do-i-create-screenshot-my-problem

I found out right now that I can sign and encrypt mails with very few people, but in most cases I get the error message...

That doesn't really make sense. In order to sign a message all you need is your private key. Why this would work for some recipients but not for others, I have no idea, and I somehow doubt that this is the case. It would either work, or not at all, regardless of the recipient.

Thank you for asking and trying to help me with this problem! I have a new laptop and I installed Thunderbird the same way I did before on my old computer, and I made the whole set-up for Enigmail as I did on my old computer. Probably, that's why I have two keys for the same e-mail address now. I then realized that I couldn't read the old encrypted messages anymore and remembered that I had saved the keys on a USB stick. I imported them and realized that my e-mail address had two different keys now, the old one and the new one. I thought I can simply delete the new one, but this caused problems, and I imported it again (had saved it before on the stick). I can reply to the old encrypted mails with encryption and signature, but I can't sign new mails. Do you know what might have happened based on this description? Thank you!!

P.S.: I found out that I can send encrypted and signed e-mails with the new signature, but I can't sent messages I only sign...

You specified that this message should be digitally signed, but the application either failed to find the signing certificate specified in your Mail & Newsgroup Account Settings, or the certificate has expired.

The error message suggests you're trying to use S/MIME for signing, which would require a certificate.

Enigmail actually does both, OpenPGP, and S/MIME. So you'll have to make sure to choose OpenPGP encryption and signing, as your post above suggests this is what you're actually trying to do. This can be specified in your Account Settings, or on the fly via the Enigmail menu item in a compose window. You'll also need to specify which keypair shall be used for encryption and signing in your Account Settings.

Presumably with the new Thunderbird installation on the laptop you've been using Enigmail PEP mode, which would explain why a new keypair was created automatically. This is particularly annoying when a keypair already exists. Therefore I'd suggest to disable PEP in your Enigmail settings.

Thank you very much! I managed to adjust my Account Settings, the only thing I couldn't find is where to disable PEP. But I've chosen to always use the new key and it's working now. Thank you again for your help!