May be needless to reply now.. but the tly file should be there. Sometimes it doesn' show up unless you click the "Media types" dropdown on the Restore dialog or may be type Backup.tly in the File name/path textfield.
. .. I got no errors, the backup worked like a charm, so it seemed.
Yes, that's the problem. It's not uncommon that the backup seems to be complete and ok... but the .tly file is not yet written in the backup folder.
There is a time lag at the end of the backup when no message is displayed and many users stop the process prematurely. Or for some other unknown reason, the backup is not complete. The last files to be written in the backup folder are catalog.buc, then backup.tly. So my advice would be to always have a look after the backup to see if the .tly is present in the backup folder. That does not guarantee you won't have other problems in the restore.
For information, the catalog.buc is a copy of the present database catalog.pse11db, where the full paths of each file is kept. Each media (or xmp) file is copied and renamed B0000001.xxx so that there is no risk of duplicates and in a very short file copy name. The backup.tly is a list telling which file copy name is linked with each internal identifier for that file. You understand why it is absolutely necessary.