Malte, I can't help, only sympathize: I could not find a way to import my 7.3 dump into a new 7.4 database, either, so I'd love to hear a success story and read the documentation informing it!
I think the debian upgrade script includes the convolutions necessary to do this - ie, preserving old binaries, etc. It seems like the PostGreSQL upgrade team did it to us again.