.. .. long but precise history of problems omitted .. The old revision 2 and the new revision 3 and higher of all TeX packages are incompatible with each other because the newer comply with the new TeX directory standard asking for a a bunch of new paths to store TeX related stuff.
You need to remove all TeX related packages and get the newest ones from your next debian mirror. Sorry for that but I wanted to keep to the standards. This will probably not happen again in the near future as the paths are there to stay for a while. I agree that the error messages are not helpful at all, there are a few 'conflicts' missing from the package control files that would have give error messages pointing you in the right direction. Nils
