Does Federal income tax withheld on a traditional to Roth IRA conversion get subtracted from AGI in calculating MAGI? If no, what happens to this withholding on a recharacterization?

Federal income tax withheld on a roth conversion is a disaster! It means that you did not convert 100% of the account. The withheld taxes are income, count towards the $100K limit, and is subject to the 10% early withdrawal penalty.

Since you did not convert 100% of the account, you can only recharacterize what you converted. The withheld taxes will be a credit on your tax return.