Yup, it happened to me. :-(
This morning, the TiVo had this message on it.
I do not believe the power had cycled.
I have the TiVo Series 3 HD.
About a month ago I got the WD MyBook AV 1TB
After replacing the useless/included eSATA cable with one I found at MicroCenter,
it has been working fine for about a month.
My PC (Computer / Disk Mgmt) does recognize the drive via the USB interface,
so at least the disk is alive and spinning in there.
Do I have a 2nd eSATA cable gone bad?!
I did try power cycling the TiVo several times, including manually delaying power up of the WD MyBook.
But I still end up at the "External Storage Missing" screen.