As per the other thread, I have the same issue and I think I've worked it out. On one of my tivos (A) I did a clear and delete everything not long after the end of service. Even though it still shows the MAK in the menu I believe it has been wiped. It still sees the name of the other tivo (B) which wasn't cleared but can't see any of its recordings. B can no longer see the name of A and lists it as DVR-XXXX.

I'll probably try restore a backup (unfortunately it's of the original 160gb drive) over the weekend to see if that brings it back.