If complex only refers to inherent complexity (and not accidental complexity and whatever other attributes were used by people before) then how is "simple is better than complex" to be read? If complex is inherent to the problem, does it mean "solve a different problem"?
Complicated = a solution that's difficult to understand due to a convoluted implementation. These can be simplified.
In other words, the difference is whether the difficulty is inherent to the problem space (complex) versus inflicted by a solution (complicated).