Are you using Time Machine for the backup?
If so it should have no trouble. Over wireless and especially on Lion could be issue.. but the backup itself not so.
Is this initial configuration? ie had one working for ages and added a new computer.. spell it out a bit?
Also spell out the exact problem. We cannot work with no info.
A1 install the widget so you can get log of faults.
Ok, I think you need to run a verify disk on the computer before you try and backup again.
And either verify the TC or start again.. just wipe it, if you haven't had a single successful backup and all attempts are by wireless. Erase and start again.. IMHO.. others will suggest just the verify but enough goes wrong that unless you are actually prepared to test the back.. and the only way to do that is a full restore.. it is nice to know the first one went complete in one go.