Thanks for the suggestion. But I don't think this is to do with permissions. Anyway as I have enabled "simple file sharing" I do not have a security tab. But since it is simple sharing (which I guess is equivalent giving full access for Everyone) my guess is that there shouldn't be an issue with permissions.
Anyway as Nicolas said I think there is some problem with the file system. As I said in previous mail I could not find any errors in the file system when I used scandisk but when I tried to delete some folders I could not do it (even via windows explorer). This is because of long file names / directory paths. So when rdiff-backup does the backup it deletes some files/folders so that it mirrors to the source and sends the changes to the rdiff folder. Probably this is where it fails. So it is not exactly due to the files that the exception log shows.
I guess when you said 2006 you meant 2009, right? because last stable version 1.2.8 was released in 2009/03/16. Anyway as I said, in the changelog it is mentioned that in v1.2.6 there is an issue under Windows for long file names / directory paths. This has apparently not been still rectified.
Anyway because of all this I tried QtdSync which is based on rsync. This seems to be working for me (it does not delete but uses hard links for differential backups). Of course I agree rdiff-backup is a great application, it is just that it doesn't suit my environment. So thank you very much for all the help and big thank you for the developers.