Hi,
sounds like an index corruption. Is this only for one client or for all backups ?
If for a single client then try a cross-check
nsrck -L5 <client> - you can use any level from 1-7 (7 will rebuild the index from tape)
If it's across the board then it may be a media database corruption so try
nsrim -X
Rgds,
KSK