I had this problem: gcc was present, but g++ was not.
Unfortunately, Gradle did not say that g++ was specifically missing, only that the GCC toolchain was not present, so I had to look into the Gradle source code to figure out how it checked for that. It was only then that I saw that I should have checked for g++ in addition to gcc.
This may affect others as well - people who use LLVM but forgot to install Clang, etc.