I'm back. Got everything working! GMail, Market, YouTube without doing a factory reset.
I tried to use the automated script but it wasn't configured to work properly for me and I couldn't make the necessary changes. Used the manual process with no problems.
Next I'll see if the Overdrive app will work now.
Edit: Overdrive does work now! Figured it was Google related. Unreal how everything is intertwined.