Thanks Matt, I've spent weeks trying to figure this out!

It does sound like it is exactly what is happening, and matches the symptoms.

Do you think there is a way to delete the offending Genre(s) from the TiVo? (And I wonder why my other UK TiVos are not having the problem?)