My environment is Windows 2K with TSM 4.2.3.1 ... yep it is old, but
hopefully in May we can upgrade :)

I have one client that is getting this mesage ( server out of storage) and
the backup fails.

The diskpool where the backups go is about 200G with caching turned on
(should hold
a couple of days of backups) and the database and recovery logs have had a
high water
mark of about 71% and 26% respectively (currently about 70% and 0.4%).

Where should I be looking for the problem?

I see nothing in the servers log files that are related.

... Jack