Jesus Fucking Christ.
I just changed my Windows Live ID from a gmail address to a new "live.co.uk" address. Of course, because you are unable to change the Windows Live account associated with a Windows Phone, I'm screwed. Christ, it's not even like the account is different, it's just the ID of the account has changed.
Xbox Live didn't have problem with the change and just signed me normally. My WP can no longer sign in to the primary account which I assume means I can no longer buy things....
A hard reset?