Comment 11 for bug 84443

The /var/lib/dpkg/available corruption and the other problems you point out very much suggest that you're suffering from bad memory, a CD fault such as a dirty drive lens or scratched disk (probably not the latter since you've tried multiple disks), a hard drive fault, or some combination of the above. Sometimes different OSes are differently sensitive to this sort of thing.