Rapidly mixing Markov chains on 3-colorings of a cycle
I got the following solution by email from Dana Randall, so any credit for the solution should go to her (which I guess means: don't upvote this answer) and any bugs were likely introduced by me.

The short version of Dana's solution is: instead of using the Markov chain I described, in which potentially-large two-colored regions are recolored, use a "heat bath" in which we repeatedly remove the colors of two vertices and then choose a valid coloring for them at random. It's not hard to show that, if this chain mixes, then the other one does as well. But a standard path coupling argument turns out to work to show that the heat bath does indeed mix.

The long version is too long to include here, so I put it in a blog post instead.