Added 4/22/13: I've rewritten this almost entirely, to correct a serious mistake I'd made at the very outset of the original proof. I think what I've posted now is correct. (end of addition)
As nvcleemp noted, one should start with a 2-coloring (Black and White) of the tree and, if the number of leaves is even, simply change every other leaf around the cycle to a third color (Red). It's only if there is an odd number leaves that we have to do something fancier. To handle that case, it's helpful to introduce a tiny bit of terminology: Let's call the vertices that leaves are connected to "buds."
We'll start with a little lemma:
If the tree is not a star, then there
are at least two buds for which the
cycle traversing the leaves passes
consecutively through those buds' leaves.
Proof:
It's easy to see that this is true if
there are only two buds. The rest is
by induction, which is easiest to
picture if you imagine the graph
deformed so that the cycle through the
leaves is a circle. Suppose there's a
bud for which the cycle does not pass
consecutively through its leaves.
Picture that bud as being at the center of the
circle and two of its non-consecutive
leaves at 12:00 and 6:00 on the
circle, connected to the bud by radii.
The non-consecutiveness means there
are other buds connecting to other
leaves on each side of the diameter
just drawn. This means there is a
smaller tree on each side (including the bud and two leaves of the
diameter), so induction applies. One
of the two consecutive-leaf buds for each
side may be the bud at the center of
the circle, but that still leaves at
least one bud on each side for which
the cycle passes through its leaves
consecutively.
We're now in position to complete the proof of 3-coloring for non-stars in the case of oddly many leaves.
Pick one of the buds for which the cycle passes consecutively through its leaves. (The lemma guarantees us two, but we only need one.) Change its color to Red. Skipping its leaves for the moment, and starting with the "next" leaf (say running clockwise), turn every other leaf Red until you get back around to the Red bud's leaves, at which point you just need to alternate Black and White. (Note, this works even for the "easy" case where the number of leaves is even.)
Note: David Eppstein has given a different, inductive proof at the cross posting noted here in an answer/comment by fidbc.
Best Answer
A graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. As Hunter's comment points out, $K_{3,3}$ is bipartite, ie two-colourable.