The largest problem I foresee with most hosting providers switching over to PHP5 are two-fold.
1.) MySQL support is no longer standard, you have to build something extra (oh no!).
2.) It will break some PHP3/PHP4 scripts which are used by both Fantastico and CPanel. I don't think hosting providers will really want to provide PHP5 until CPanel fully supports it.
There are some hosts which host BOTH PHP4 and PHP5, but you have to request that you use the PHP5 server - they do not mix the two servers...it'd be too much scripting (a file at best?) to auto-switch people from PHP4 to PHP5 permissions for the same server.
Alas, I highly doubt it'll happen fully for a few years, just like Stephen stated...however, I gave a few more reasons.

Yes, it is technically easier than hosts might think, but it would add a serious headache for them that they really could care less about (i.e.: wouldn't want).