Interesting case here where bprestore commands issued with a start date that is long before the date of the backup causes jobs to stay queued for a long period of time, sometimes many hours. Our backups are project-based where a project management system stores all the appropriate info for billing and other purposes.
Adjusting the start date to the date of the backup (by querying the project management system for the end date of the project, which is when the project goes to tape) seems to address this issue, and the bprestores immediately go active.
If you really need to know why it's taking so long, you will need to dig into bprd and bpdbm logs on the master server and monitor master server resources.
Extended searches may cause bpdbm process to consume excessive resources on the master server.