Today I was trying to do a backup to my WHS and I was getting the message on my client:

Backup is waiting on (cleanup).

After quite a long time, it was still on this message.

I did some investigating on the server and saw that 45 minutes earlier my server had kicked off a backup cleanup process.  This was indicated in the event viewer under “Homeserver”. 

Task Manager also showed whsbackup.exe doing a lot of work.

So, if you run into this, just wait a bit and when the server is done with the cleanup the client backup will start like normal.