Another thing to think about with Verizon is that he'll have to switch to a data-limited connection (or even a Share Everything plan...ugh) when he upgrades to the Windows Phone. If he goes all the way to Share Everything, that's $100 per month for a decent amount of data (2GB), though of course calling needs will be met. More likely though is that he can just grab the $30, 2GB per month data pack and keep his normal plan (though that might actually be more expensive than Share Everything, depending on how many minutes he chews through).
...then there's Sprint, which will have Win8 phones soonish (I guess) and unlimited data, on a plan that's $80 per month since mobile calling sounds like most of the minute usage. You can even shave another $10 per month off (and get another 50 anytime minutes) by going to sprint.com/everythingplus and using Russ.S.McGuire@sprint.com / 383 for the credentials (yes, that hack still works, and is pretty much sanctioned by Sprint at this point).
As others have said though, check coverage beforehand. It might not be worth it to switch if you go from LTE 90% of the time to a hodgepodge of LTE, 3G and roaming 1x.