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 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 book 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*."