So, Backup Exec is telling you you've ran out of space. So you've adjusted retention times, erased a library or 2, or added some more space etc... Yet it still thinks it is out of space.
The solution? Simple. Under 'Devices' right click on the Backup To Disk folder which has the low space warning on it, choose Pause. Repeat, and unpause. Done.