Actually, mine turned out to be a DHCP issue. After posting my issue above, I left Wireshark capturing anything that my TiVos broadcast for a day. Roamio has two IP addresses assigned to two consecutive MACs. One of them changed its IP during the day, but I have no idea why the DHCP server did not re-assign the same IP. After that change, Mini could see My Shows, but could not play any of them. Live TV was also not working.
This happened with a Netgear router, so maybe other routers would have been smarter about assigning the same IP to the same MAC even without static allocation.
Also, I do not know why Mini could not play after Roamio's one of the IPs changed, it should've caught the new TiVoConnect beacon in my opinion (sounds ignorant?).
In short, I went to my router settings, assigned a static IP to all TiVo MACs including even the Mini. It has been working just fine since then (it's been 2 days). Yay!