If the OS cannot recognize the external drive containing the TimeMachine backups, it is possible that the backup was done on a drive which does not support upper/lower case, while the file system of the new OS does.
Unfortunately it seems impossible to force an OS which installed on a case insensitive drive to perform its TimeMachine backup on a case sensitive drive. Even when you erase and format the disk accordingly, the file system is changed on the moment you tell TimeMachine to use it as a backup disk.
Any workarounds to this problem are highly appreciated! (Suppose there must be some, otherwise people with older machines would not be able to upgrade to new ones)
If you want to be sure that the issue is related to the filesystem of the disk, try to execute the migration from mac to mac (both have to be in the same network and MigrationAssistant must be started). If this is the problem, the machine will be found but an error message will explain why MigrationAssistant can't migrate the data from one machine to the other.