I had to add registry entries to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows Home Server\Transport\Clients for the backups to be visible. The values could be discerned from the {GUID}.Machine.configdat file in the backup folder. I had to add the Clients key, a subkey under that for {GUID}, and then I added all the string values from the {GUID}.Machine.configdat file, though I am guessing only the first 2 mattered. I am surprised that both the backup service did not rebuild these registry entries and that the document I linked above did not mention these entries.
It is also worth noting that I also needed to attach a client to WHS to do the restore. You cannot do the restore from WHS alone.