Once you've run out of disk space which has the Client Computer Backups folder you can't start the Windows Server Client Computer Backup Service and consequently backup your client computers. It happens when because the service finds the needed file corrupted. Obviously it wasn't written successfully.
In the C:\Users\All Users\Microsoft\Windows Server\Logs\backup-MMDDYY.log you can see this data like following:
The Windows Server Client Computer Backup Service encountered the following error:
Error code: 0x26
API name: unexpected EOF
File: D:\ServerFolders\Client Computer Backups\Commit.dat
Error: Reached the end of the file.
The Windows Server Client Computer Backup Service failed at (438) of (d:\wssg_src\hsbs_colorado\backup\pc\util\diskfile.cpp).
To fix it you have just to delete the Commit.dat file from Client Computer Backups folder and restart the service.