One slight distinction between the two is that if the complexity was in some sense avoidable, 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 "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 even less comprehensible because of the author's complicated explanations."