I had this problem once before... I tried many times to redo everything to no avail.
What I did try though was running the Verify tab and that was the issue... All my apps were backed up but they were ALL corrupted. I dont remember what rom I was on but i experimented and certain roms have issues with TBU.
So, try verifying the back ups. if the check throws you tons of red text errors, chances are that's your problem.
I had this happen as well (on my install of GummyJar). I'd used TB many times before, but all the backups I made just before I installed Gummy ended up corrupted when I went to restore them into the fresh Gummy installation.
I did the batch verify (suggested by the dev via twitter), and it showed all my most recent backups as corrupted. All the previous backups were fine, so I was mostly able to restore those. The dev was done replying to me by the time I asked what might have caused the corruption.