I have done this for at least 25 people and for myself 5-7 times. I can tell you this is one of those things that really depends on all of the above. also the size of each account. The load on the machine is also important. If it's a bare metal restore from healthy disks, you may aslo consider a fresh OS and then a rsync of the needed files and folders from the old live drive. If it's coming from backups, the speed would all depend on how big the accounts are. What I typically do is restore the larger accounts first. (assuming the load will be less on the system without any traffic flowing) and then gradually restore to the smallest accounts last. I do them in batches typically like this and I typically watch the entire process. It's not fun.The best way to determine the time is to do a mock restore from your backups onto a test machine to see how long it takes.
The issue here with providing any sort of estimate for you is that every server has different hardware, disk space, backup types and speeds for the network. As such, it's impossible to give you any sort of timeframe. The best suggestion would be to simply do a test restore to a machine that has the same specs as existing one to see how long it takes.
Additionally, this will ensure you know what problems may arise during the restore process, and you'll be better prepared on what steps to take when/if something does fail and you have to do a restore.
As a minimum, the traditional sysadmin "rule of thumb" is that restores take 2 to 3 times more than the backup time. No way is 1.5 enough. This is of course a "rule of thumb" so, as the wise posters above have said, hardware and system load will change your results a lot. Under some scenarios, I could envisage that reload from cpbackup tarballs could take up to 10x the backup time.can we say restore time = 1.5 backup time.