I have used to have this issue too. a reboot fixeds it for me.
I have two tivos and it only effects the one with the external HDD. do you have a external HDD ?

Charles