I'm used to using a number of different GCC versions for various targets, cross-compilation or native, and most of the time, those headers are part of the GCC's distribution. But digging a bit deeper, this would not be strictly a problem with GCC indeed.
For instance, if you're using GCC for ARM-Cortex M, the standard headers are usually provided by newlib.
If you're using other targets, it depends. But if you're not doing "native" compilation on Linux (or similar environment), there is often NOT a common 'include' path - each compiler has its own stuff for the std library. It may come from newlib, glibc or yet other implementations.
So it looks like the problem lies with newlib - and some other implementations - rather than with GCC itself. I confused the two as they often come as a bundle - unless again you're strictly on native Linux.
Why a number of implementations of the C srd lib, including newlib, do not define the CMPLX macro, is now the question.
But what the compiler implements, and what the std lib implements, for complex numbers, is still a bit involved. There's of course basic support for complex numbers directly in the compiler itself, not requiring the std lib, for easy to understand reasons. (Otherwise you wouldn't have access to arithmetic on complex numbers with common operators in C, for instance. C does not have operator overloading. =) )