Customer, the state tax refund and its status as taxable doesn't have anything to do with your Roth recharacterization. Apparently, if you recharacterized the portion of the Roth before the due date, then you should not have paid taxes on that portion---because it is treated as never having been converted.
When an individual deducts state income tax in one year (2008) on his federal return, and then receives a refund of that tax, the refund is taxable as a recovery, up to the amount that it allowed the taxpayer to receive a tax benefit the prior year. You are not paying tax on this twice. Many people think that, but it is not the case.
For example, If your standard deduction for the federal government in 2008 was $10,000, and your itemized deductions were 15,000, then your itemized deductions were $5000 greater than the standard. Then, when you receive a portion of what you deducted back (the state income tax that you took a deduction for in 2008), you have to claim it as income up to the amount that it gave you a tax benefit.
I know it is confusing, but it is your state tax refund that is taxable to the federal government, not your Roth recharacterization.