Okay, I finally got it working, but I'm not sure what the problem was...
I found someone saying that using Pacifist one should be able to extract separate files from an OS X installation disk. Using Pacifist I was able to extract Preview.app, copy it to my Desktop. I tried opening it from the Desktop and opening a file, it worked!
Now, since it's not possible (I couldn't find a way) to delete Preview in the Applications folder I right-clicked to Get Package Contents. I did this for Preview on my Desktop (from the installation USB disk) and copied all the contents from Preview (Desktop) to Preview (Applications).
Apparently this solved my problem. I have searched to see if anyone else had the problem, but I could only find problems with Preview under Lion. Maybe Preview is corrupt in my ML installation? Strange, because I tried to download it again.
I have to admit I am really quite surprised to see something like this happen, and to be honest my initial ML-happiness is somewhat reduced now...