Hm. Do you have OnyX? The only other thing I can think to suggest is to use OnyX to look at your Safari settings. Under Parameters/Safari is the check box for "Automatically open pdf files is Safari." I unchecked that selection and PDFs now open in Preview.
Also, in my experience, the first thing to try whenever this problem crops up is to empty the Safari cache.