One subtle distinction between the two is that where the complexity was in some sense introduced, it is probably more common to use "complicated" than "complex." For example,
The instructions were way too complicated.
It is of course true that the instructions were also complex, 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. As a result, "complicated" sometimes has a negative connotation, effectively meaning "unnecessarily complex."
Quantum mechanics is an inherently complex subject, but the textbook was an even tougher slog because of the author's complicated explanations.
However, as others have said, there is a large overlap in the use of the two words.
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."
