Yes, i would recharacterize into a Roth.
What you need to do is make sure you are both maxing out your 401k's and HSA's if you have them. This will lower your adjusted gross income and hence, increase your deductibility of a tIRA, which will further reduce your taxable income. Only after you do all this, would I even consider a Roth IRA.
Personally, I think Roth's are a waste of time for an early retiree, and I wrote about our experience on my blog. We withdrew all of our principal a few years back, and I regret it zero.