Something simple and yet complex...

Most people would probably just use the description 'harder than it looks'. More esoteric, and a noun phrase, is 'Russian doll problem'; this would seem applicable to complex problems involving logical reasoning or dexterity rather than complex emotional problems.

The term simplism refers to the approach to such a problem.

According to MW:

the act or an instance of oversimplifying; especially : the reduction of a problem to a false simplicity by ignoring complicating factors

The adjective simplistic is found much more often and is used to characterize the actor's efforts.

See ngram simplism/simplistic:

(The drop after 2000 is curious unless it is a data collection artifact.)

Pitfall ("a potential problem, hazard, or danger that is easily encountered but not immediately obvious") looks like an appropriate term. Also consider adjectives like deceptive ("misleading, likely or attempting to deceive "), subtle ("Hard to grasp; not obvious or easily understood; barely noticeable"), tricky ("hard to deal with, complicated"). Figuratively, you might refer to a snare ("(rare) A mental or psychological trap; usually in the phrase a snare and a delusion"), a trap (in sense "A trick or arrangement designed to catch someone in a more general sense"), or deadfall ("A kind of trap for large animals") or quicksand (in sense "Anything that pulls one down or buries one metaphorically").

One phrase I've heard is deceptively simple, although there seems to be some debate about whether that refers to something that seems simple (but is in fact complex), or something that seems complex, but is really rather simple.

Six years ago, an online group debated this very phrase, and never really reached a consensus. You can read their debate by clicking on the link, but I think one contributor summed it up best by saying:

it's one of those phrases that can mean two opposite things, depending on context

The Free Dictionary has an interesting usage note on this deceptively complex word pairing; it shows that even experts disagree on the matter. Another blogger has warned, don't use this phrase in a vacuum; it won't be clear what you're trying to convey.

Sometimes, though, the intended meaning can be easily inferred from the context:

Golf is deceptively simple, endlessly complicated. (Arnold Palmer)

I'd say this question is deceptively simple, too – but I'll leave it up to you to figure out what I mean by that.

While it isn't an exact fit, the Japanese (as usual) have the word shibui to represent something which is simple, yet complex. Howeer, the complexity that it alludes to is not used to connote difficulty. Instead, it represents qualities such as subtlety, harmony, elegance, and profundity.

Can of worms is a phrase that's often used to describe complex situations or unforeseen trouble ahead.

I’m reminded of project work where you might qualify an effort as, “open ended” or “unbound”, relative to time estimation.

Or a tangled, ensnaring, or snowballing task - or even invoke the "One step forward two steps back" idiom.

(That said, I up-voted Can of Worms, which nails the counterintuitive nature of it, and Deceptively Simple, which is just a great post. These are just extra ideas for you.)