I solved the problem eventually with help from this post on the Google Android forum:
http://code.google.com/p/android/issues/detail?id=21031
For me personally the biggest issue seemed to be solved as follows (qutoe from comment 25 in the forum post)
"I seem to solve the problem with .apk files not being built automatically until run/debug is used (comments #10, #11 etc.). Go to Windows -> Preferences -> Android -> Build and uncheck "Skip packaging and dexing until export or launch" then restart Eclipse. Works for me."
But there is other useful material there. Different people with different projects seem to have different problems with this setup.
I still don't understand the change in the classpath, but it doesn't seem to matter.
In addition, I found a discussion of installing the ADT with Eclipse Indigo which was helpful here in Stackoverflow:
Eclipse Indigo - Cannot install Android ADT Plugin
I also found that I guess because of various uninstalls/reinstalls, for some reason it stopped excluding my .svn directories from the sources. This Stackoverflow post was helpful with that:
Why is eclipse trying to copy my .svn folders from src to bin, and how can I make it stop?
Finally: a tip for really and truly uninstalling Eclipse - everybody says there is no uninstall, and there isn't, but there is a directory that Eclipse leaves in your home directory (in windows 7 under c:\users\) called .eclipse -
Zap it if you really want to start fresh.
In addition, for less extreme measures, there is Project->Clean inside Eclipse, and you can invoke eclipse with "eclipse -clean" for additional cleansing effects. No idea what, but various helpful people along the way suggested trying that to solve problems.
Ah yes - when I first installed Indigo and tried to build, I got a warning that my Java Compiler Compliance level was not up to snuff, which was simply not true - I have only Java 1.6 installed on my machine.
See this post for somebody who had similar experience:
http://marakana.com/forums/android/general/374.html
For me, what worked was simply going to Project, Properties, Java Compiler, then click on Configure Workspace Settings, and click on Ok in the dialog. Didn't need to actually change anything. Just showed it that everything was ok!
Eventually I indeed did clean out my Eclipse and Android installations (including the aforementioned .eclipse directory, and there's also an .android directory in your home directory which you may want to erase if uninstalling the Android SDK Tools doesn't do that - this actually is uninstallable). Installed everything from scratch and then used the additional information provided above and now it's building my APK.
I hope this saves somebody the hours I spent getting my build back in shape.