Thanks Jernej for your quick reply. Really sorry about the long delay in repling back, I was away and was busy with so many things. I guess you refering to the line "Warning: Could not restore file DVD 1/Celine Dion/Celine Dion & R Kelly
- I�m Your Angel.mp3!" in the error log when you mentioned about the Unicode characted. But strangely the actual file name is ("Celine Dion & R Kelly - I´m Your Angel.mp3"). So as you can see there are no Unicode characters. Anyway if this is something to do with characters that python cannot handle I guess it will not be able to handle it even in the initial backup. But the initial backup seems to be working all the time, only the incremental fails.
I wonder whether this is a bug in rdiff-backup. For me it seems more like that rdiff-backup is having some problems with NTFS permission (read only etc.) Anyway this is just my guess.