Within the "Backups | Active Directory" section of the Recovery Manager for AD console, right click on the backup required to perform the restore and chose "Delete Unpacked Components". Go through the Online Restore Wizard again and if prompted to index, chose Yes. This may take some time and the console may go unresponsive during the indexing, but the searches will be much faster when finished. If you did not get prompted to index, move to workaround #2
Its possible that the console does not prompt to index, if this is the case follow the below steps to force the console to prompt to index:
Install Recovery Manager for AD on the same Operating System version as the Domain Controller. This will not require indexing and will allow you to avoid the index time or search time.