Is this a S3/TivoHD w/ cablecards? Check your cablecard setup menus, conditional access screen, see if it's a pairing or authorization problem.
Follow Tivo's Cablecard troubleshooting
page. Might need to call cable company to fix.
Also, it's conceivable that Tivo thinks the lineup changed but your area hasn't actually been upgraded yet. Check the local HDTV info section of avsforum.com for your area, see if people in your neighborhood are getting the new channels.