When making a major version change, like from potato to testing, you should use apt-get dist-upgrade. Not just upgrade. dist-upgrade is designed to attempt to intelligently handle dependencies when changing from one major version to another. I'm not saying that this would have prevented your tragedy but it might have handled the dependencies better. I know that it worked fine for me when going from a mix of stable and unstable to potato when it froze. This also fixed a lot of problems I was having due to running a mixed system. The only thing I don't know how to do is un-upgrade a package. I usually just live with it until it is fixed. Thanks to the Debian community, this usually isn't too long.
In saying this, Debian still has the better package management system so far. I spent ages trying to get KDE installed on my daughters Mandrake system but being RedHat-based it kept installing packages and then telling me the missing dependencies, which I then installed only to learn about more missing dependencies. I followed this loop for over 5 days before I re-formatted her Linux partitions, installed Progeny and did an apt-get install task-kde from Ivan's site and had her new system up and running before she was home from school! I think that you might have been better off just installing testing directly, but I am guessing that you have a potato CD that you installed from. Here are a few tips I used when changing to potato when it froze. Change your source.list file from stable to woody. I prefer to use the actual version name to be sure that I am upgrading to a known version. Since stable/testing/unstable can and do change from version to version. By using the proper name you can avoid nasty surprises. Run apt-get update to update your list of packages now that you are pointing to woody. run apt-get -s dist-upgrade. This will only simulate the upgrade and give you a list of everything that will happen. You can re-direct the output to a file if you wish to print it out. Please study this carefully. This will show where the last upgrade went so wrong. Going from potato to woody will involve a lot of packages. You might want to try incremental upgrades instead. Pick a few packages and run apt-get install <PACKAGE>. This will upgrade the named package and any dependencies it requires. I connect with a 56k modem on per-minute charges. Even though apt-get dist-upgrade can continue from where it left off, it will not configure anything until ALL packages are down-loaded. Sometimes it is easier to upgrade a few packages at a time, as many packages will have to be configured and will often ask if they should replace existing config files. Other tips for upgrading to testing should be available on Debian's site. I don't have Internet access right now so I can't point you to a proper page, but have a look around, especially the installation pages. There should be some good info there. I hope this goes better for you than the last upgrade did. I'm sure that others can offer even better advice, but this was my experience from the last major upgrade. Cheers, John Gay