OK, ich hab's.
Also, wenn man in VirtualBox einfach die ISO im rescue-Modus startet, bekommt man irgendwann genau das Bild, das KDBCALLS gepostet hat. Also nix mit Grub neu installieren.
Jetzt, wo ich die Lösung gefunden habe, ist das aber auch ganz klar. Wohin soll denn Grub neu installiert werden? Es gibt doch überhaupt noch keine Partitionen. Daher kann man natürlich auch im Schritt vorher kein root-Dateisystem auswählen. Auch das gibt es ja noch gar nicht.
Ich habe dann genau das ISO (aktuelles 6.0.4), mit dem ich es in VBox probiert habe auf CD gebrannt, meinen Rechner damit im rescue-Modus gebootet und siehe da: Alles genau so wie es sein soll.
Also root-Dateisystem auswählen und im nächsten Schritt gibt es dann auch die Möglichkeit, Grub neu zu installieren.
Fazit: Es muss natürlich mit dem ISO in ein bereits bestehendes System hineingebootet werden, sonst geht es (natürlich) nicht. Dies geht auch in VBox, man muss eben nur ein bereits vorhandenes Debian-System auswählen und dann dort die ISO booten.
Ich habe das übrigens mit den Buisenesscard-Images für Squeeze und Wheezy probiert, jeweils in 32- und 64bit. Geht bei allen.