If it's a next tape issue, you may wish to use the mminfo command to generate a report to let you know what tapes are set to recycle etc.. I have encountered this problem in the past and now have a small batch file that we run each morning / evening to let us know what tapes are set to recycle, manually, automatically, what pool they belong to and so forth. We also use this batch file to generate a list of Default Clones to send off-site.
I'd be happy to forward a copy of this script if you are interested. This batch is designed to function on an NT system. I am not familiar with UNIX or other, based systems. It also allows us to determine what tapes we can safely label, if we need to.
Legato should behave in such a fashion that it will look for unlabeled tapes to use first, then look for tapes that are recyclable. If there are none of the above, I have seen the server hang in the fashion you describe.
Good luck,
cfowler