Are you trying to back up to disk or tape? Is the Append to media option selected?

More details, please! I usually back up to disk due to the 'media family' stuff that backup systems now seem to enjoy torturing us with.

-R!