Added 4/24/13: I tried replacing this incorrect proof with a correct one yesterday, but for some reason was unable to do so, so I posted the correction separately. There is no reason to read any further here, except perhaps for the link to mathoverflow. [end of addition]
I posted the following proof at https://mathoverflow.net/questions/128169/3-coloring-of-specific-planar-graphs where the problem was cross posted (as fidbc noted in comments here and there):
Let's call the vertices that leaves are connected to "buds." Note that the cycle traversing the leaves must pass consecutively through the leaves of each bud. This makes everything easy.
As in nvcleemp's answer, start with a 2-coloring (Black and White) of the tree. If the number of leaves is even, there's no problem changing every other one to a third color (Red). If the number of leaves is odd and the tree is not a star, there are two possibilities: either one of the buds has an even number of leaves, or all the buds have an odd number of leaves and there are an odd number of them (and that number is at least 3).
The case where there's a bud with an even number of leaves is easy to handle: Take the portion of the cycle that doesn't contain that bud's leaves, note that it is a path connecting an odd number of leaves (since odd minus even is odd), and change every other leaf's color to Red, starting with the first and hence stopping with the last. Finally, change the selected bud's color to Red and alternate its leaves Black and White.
The case where there are an odd number of buds, each with an odd number of leaves, is a little trickier. For the moment, retract all the leaves down to their buds, dragging the cycle with them. Some of the edges of this "retraction" cycle might coincide with edges connecting buds of the underlying tree, but they can't all coincide -- there must be at least two "consecutive" buds on the retraction cycle that are not in fact connected. (This is where non-starness is assumed.) Now color these two buds Red. Finally, undo the retraction of the original cycle's leaves and, starting with the first first leaf of the first non-Red bud, color every other leaf Red. Since there's an odd number of buds each with an odd number of leaves, this changes the last leaf of the last non-Red bud to Red, leaving only the leaves of the two Red buds, which can be colored alternately Black and White.