What are the characteristics that make complex problem solving complex?
The complexity of the environment certainly is an issue. According to AI - A modern approach, the environment may be


observable / partly observable
deterministic / stochastic / strategic
episodic / sequential
static / dynamic
discrete / continuous
single agent / multiple agent


See also WikiDoc for a short overview.
In my oppinion, these criteria apply also to human problem
solving.

Another issue is the type of problem to be solved.
A measure for complexity may be the number of steps
that must be anticipated to solve the problem, e.g.
solving a chess endgame is more complex than solving
tic tac toe.