Hopefully someone else will also have ideas, but I'm wondering if Preview is waiting on the disk, is chewing up the CPU or just sitting there but not showing anything. If you send it to the end of the file does it go there instantly or does it hang up?
I'd suggesting loading Activity Monitor and sorting by CPU usage, along with displaying disk activity at the bottom and see which one (if either) appears to be where Preview is concentrating while it's hung up.
It might relate to the preference file (weird things sometimes hit there), but I suspect you could eliminate that if you temporarily created another user account and opened up a problem PDF there. That way you could see if the problem seems linked to the account. If it does, you could try deleting the Preview plist file in your user Library folder (Preview should recreate it if it's missing).
If you create a pure text PDF of about the same number of pages (if you have a large text only document you could import it into TextEdit, Pages, Word, etc., copy/paste it into itself enough to get 1000 pages, then print to disk) you might look at that as well. It's possible the file contains some graphics structure that might be slowing things up, though I'd think that would only show if you passed by a page with that sort of graphic.
I suppose one final test (though I don't really like it) would be to obain Adobe's Free Reader for the Mac and see if that has the same problem or not. I don't like that because Adobe may want to claim all PDFs by default, forcing you to swap it back if you want to go back to Preview, but it might help.