Any time you get a completely new channel, you'll have to let your box or DTV set update. The PSIP information, with it's channel allocation tables, programming tables, etc will have to be in there for it to decode that particular station.
Some sets do this without rescanning, some need an updated scan, some need to completely re-scan.
I've heard that TV DXers liked the Zenith DTT901 (which may be unavailable...I don't see it listed at Solid Signal) because you could just enter the RF channel number directly, and it would scan that particular channel for new PSIP.