I've been getting this message very day for the past few months. Even with the replacement unit.
Last nite when I switched over to it all my channels had vanished and I had to do a rescan to get them back..
This getting to be a pain and hope this new replacement TiVo is not developing a problem..