This may seem like a strange question, but I'm rather curious about how this is handled here. Let's say a priest of Gargauth has been playing with a priest of Tyr for a while. The Gargauthian has been subtly molding the Tyrran around various staple points of Gargauth's dogma: man is naturally evil and would turn on his fellow man in an instant, the pursuit of power is the ultimate purpose in life, etc. Through a carefully arrainged plan, he manipulates his friend into doing something that would cause him to lose favor in Tyr's eyes to the point that he would no longer grant him spells. The Gargauthian then makes an effort to get his friend, who is quite distraught that he is no longer beloved by Tyr, to join the priesthood of Gargauth.

If he succeeds, does the former priest of Tyr get to remake his character to fit the appropriate domains?

I don't have a problem adjusting a character to reflect a change of faith if the change of faith is earned in game. I would imagine that a priest changing his patron god would be a major change.

Re-making a character entirely, for any reason, really should be avoided if possible, unless arranged specifically with a DM. A newly rolled-up character is a new character.

I am agreeing with Song of Orpheus -- I meant I would help adjust the current character, not have the player remake to reflect the change of faith.