Anyway, I don't know 1) what OS do you use and 2) what TeX distribution you have.
Try in terminal $ kpsewhich preview.sty
Also, can you public somewhere your .emacs file with relevant settings?
I am AUCTeX user but I don't use preview at all but I tried on some of my documents: 1) add "preview-latex.el" to my .emacs (according to manual) and 2) w/o changing anything in document run C-c C-p C-p in Emacs. Further, I looked with _region_.log file and found that preview.sty from TL2011, installed system-wide, was used.
--- WBR, Vladimir Lomov
-- Support bacteria -- it's the only culture some people have!