One subtle distinction between the two is that if the complexity was in some sense introduced, I think we would be more likely to use "complicated" than "complex." For example,
The instructions were way too complicated.
It is of course true that the instructions were also more complex than they needed to be, but the silent implication in using "complicated," the past participle of "to complicate," is that somebody caused the complexity, as opposed to it being inherent in the subject.
Quantum mechanics is an inherently complex subject, but the book was an even tougher slog because of the author's complicated explanations.
Also, the idiomatic retort "It's complicated" is a sort of defense or apology for not being able to give a simple, and often expected, answer:
"What were you doing with Teresa? Don't you love your wife?"
"Yes, but ... it's complicated."