Why is the Jordan Curve Theorem not "obvious"?

There is exactly one way in which one can convince oneself that a statement is not obvious: try to prove it and look at your attempts very, very critically.

If you think you can come up with a proof of the curve theorem, edit it into the answer and we can help you dissect it :)

Later. Asaf observes that it may be the case that you are refering to "intuitively obviousness". Well... I tend to think that when someone says something is intuitively obvious without having a specific proof in mind, he is just waving hands in words. But there are two observations one can make which are independent of that.

First, the full Jordan curve theorem deals with arbitrary closed curves, and here ẗhe word "arbitrary" includes things that one usually does not think about, curves so complicated that one cannot make accurate pictures of them, so it is rather unlikely one has any intuition about them at all (at least, when encountering the theorem for the first time) This is a situation that comes all the time: one thinks a statement is intuitively true only because one is not familiar with the cases where it is not clearly true at all. One's intuition is built upon our experience, and since our experience is, by definition, limited, our intuition is limited, too.

In any case, I would suggest you try to prove the version of the Jordan curve theorem which deals with piecewise linear curves, that is, with polygonal closed curves (with finitely many segments). In this more restricted situation, we have eliminated all the wildness continuous arcs can have and are left with a geometrically sensible situation. But! It is nonetheless quite not obvious how to prove the theorem in this simple situation either, as you will find out when you try. (This version can be proved without the machinery used to prove the general theorem, though)

The Jordan Curve theorem is actually pretty easy to prove if you assume the curve is smooth or piecewise linear. The difficulty arises when you try to handle the general case. This includes nowhere-differentiable curves like the boundary of the Koch snowflake, and even wilder curves which can't even be drawn by hand, like Mariano says. It's kind of a magic fact about the plane that simple closed curves behave nicely enough for the JCT or Schoenflies theorem to hold. Actually JCT holds for any sphere $S^n$ embedded in $\mathbb R^{n+1}$ by Alexander duality, but the Schoenflies theorem does not (when $n>2$). Alexander's horned sphere is an example of $S^2$ embedded in $\mathbb R^3$ whose complement is not simply connected. Another phenomenon that "magically" doesn't happen in the plane is the phenonemon of wildness. There are embedded compact arcs in $\mathbb R^3$, such as the Fox-Artin wild arc, which have non-simply connected complements. So you can never straighten these arcs out. However in the plane any arc (or simple closed curve) can be straightened out by an ambient isotopy.

Edit: I am including a sketch of the proof in the case of a polygonal curve, following Stillwell. The smooth case can be proven by a similar argument.

Let $p$ be a polygonal curve and let $\mathcal N$ be a tubular neighborhood. Then $\mathcal N\setminus p$ has two components. (Otherwise it would be a Möbius band, which would give a non-orientation preserving path in the plane, a contradiction.) So $\mathbb R^2\setminus p$ has at most $2$ components since any point in $\mathbb R^2\setminus p$ can be joined to $\mathcal N$ by a path.

Now we show that there are exactly two components. Pick a direction which is not parallel to any segment of $p$, and consider the family of lines $\{\mathcal \ell\}$ in the plane parallel to that direction. Define the set $\mathcal O$ to be the set of points which lie on the unbounded component of any $\ell\setminus p$, or which are an even number of crossings from the unbounded component. Define $\mathcal I$ to be the set of points which are an odd number of crossings away from the unbounded component. The crucial lemma is that each of these sets is open. (Note that touching a vertex does not count as a crossing.) This can be seen by examining the ways in which the line $\ell$ can meet the polygon. The only somewhat subtle case is when $\mathcal \ell$ meets a vertex and both adjacent segments lie to one side of $\ell$.

Now we conclude that $\mathcal O$ and $\mathcal I$ are a separation of $\mathbb R^2\setminus p$, so the complement has at least two components.

I think perhaps the biggest thing that blinds one's intuition is that when one imagines embedding a circle in the plane, it's very easy to "lose the plot" and instead imagine embedding a disc in the plane, with the circle on the boundary. So not only do you see immediately the inside and outside, but you also see the Schoenflies theorem -- that a circle in the plane bounds a disc.

A game that might help you check your intuition would be to get someone else to draw an extremely complicated simple closed curve in the plane, and then see if you can determine whether or not it has an "inside" and "outside" quickly. In particular, see if you can quickly judge whether or not parts of the diagram are in the "inside" and "outside", and then check more carefully to see if you were correct.

This game can be made more complicated by there being more than one disjoint simple closed curve in the diagram. What happens then? And so on. I suspect that until you find the germ of the proof, this puzzle has much the same shape as the kind of "maze puzzles" you see in comic sections of newspapers.