While I too hate virtual channels, I know that they are not going to go away.
But, that said, Kelly's point about the cost, unfortunately, is very real. It costs millions of $$$ to rebrand. If the station only changed their real channel only once, I'd say tough. There are stations that have changed channels more than once.
Our local Fox affiliate went from 47 to 11. But, the owner, Sinclair, wanted all of their stations off the VHF band. Viewers in this market were having trouble getting 11, but not having issues getting the UHF channels that were broadcast from the same tower. So, after a long period of time, Sinclair finally got their UHF channel (49 I believe). It cost them a lot of money to go to 49. They couldn't use the old waveguides for 47, as they were cut to only work with 47 (the length). New antenna needed as well.
So, this particular station (actually Sinclair) would have spent a sh!tload of money rebranding to Fox11, only to have to do it all again a few years later as Fox49. And we all know how cheap Sinclair is. So cheap that this station is so low on the Sinclair totem pole, that the plant is still analog.
What I hate worse than virtual channels is multicasting. HD image quality is suffering because of all those SD sub-channels.