Thanks a lot for your comments!!
Darthballs: Unfortunately I will not be doing this to the entire movie, there's no way I can get time to that when I only get to play with the computer a couple of hours per week. But I would like to try out a small sequence, maybe the boarding of the Tantive, since I really like how it turned out. If it works in motion, I would be happy sharing the Fusion project to anyone who want to have a go at the entire film, or I could setup a similar project in After Effects 7 if someone is curious

Editous: The match thing works automatically for the first brightness and contrast pass, but to apply the colours themselves I use something similar to a colour transfer mode in Photoshop, I simply put the original video on top of the old one and transfer the colour down. For that I need a perfect match to avoid any bleeding. And that brings me to the final issue mentioned by Darthballs; you can't do a proper transfer where the elements have been changed. But Fusion lets you do histogram matching of colours as well, but it's not as accurate as just matching the contrast. You can get quite far by just doing that.
As soon as I have a small sequence colour-matched I'll post it here. I'll just have to finish another movie project and clean up some hard disk space first

Edit: By the way, if there are anything else that would be cool to do - please give me suggestions. I'm planning a series of tutorials on my new website, and stuff like this is great for learning.
Cheers,
Rune