Newly installed app won't run due to Apple not being able to check it for malicious software. What is the issue?

If you really want to open an app that hasn’t been notarized or is from an unidentified developer:

Control-click on the app then select "Open" from the pop-up menu instead of just double-clicking.

But do that only if you want to open a well-known trusted app. I use that shortcut to install a new version of exiftool, for example.

<rant> On the other hand, I wonder why Apple notarizes "cleaner" and virus apps etc and allows them in App Store when they just introduce obscure errors and bad user experience </rant>

What is the app and what exactly is the error message?

Mac's refusal is a security feature designed to help keep you safe.