I get these too, and then the server crashes after a couple of hours of these messages. Had to switch backups off. I'm hoping to change to a faster server, and then turn backups back on.
I believe it has something to do with race-conditions in some kernel versions. Two questions: are you running on older hardware, or something very new? Secondly, what filesystem are you using on the external hard drive - FAT32, ext3, something else?
-- JJ