This seems to be a common problem - happens with my seagate travan drive with a new tape. First time you try and do a backup, it tries to write to block 1 and fails. Second time round, mine tries to start at block 192 and everything's fine. I've never tried a restore though, so god only knows whether that'll work...