Hi,
First, how big is the restore? because if is too big, u will need to change the buffers on the media server and is always important to know if the backups was multistream and/or multiplexed, that can increase the time response and cause some other problems.
Is the client able to see the master/media server? try to telnet <client> bpcd from the master just to be sure.
How are the tape drives? are clean and healty? check on the bptm logs under the media server, maybe is a drive issue
Hope this bring u some ideas to fix the issue.
Regards.