It's a large Wordpress multisite installation, using subfolders for the individual blogs, not domains. We are running version 3.1, and preview posts doesn't work. When I press preview I get the 404.php page. Nothing in the log files that caught my eye, all plugins disabled. Sometimes I get an error message about insufficient rights when I press preview. I'm running out of ideas to try.
When posts are being previewed WordPress appends a query string to the end of the url.
The permalink settings are not applied until the post is published. While the post is in draft status the preview link will be yourdomain.com/?p=1119&preview=true where p=xxxx is the post id number.
Once the post is published and you make changes and want to preview, the preview link will be
Where %year%/%postname%/ is your permalink settings and preview_nonce is a security feature to prevent others from previewing your posts.
Can you give us the URL that the preview post link is going to. Then when clicked give us the url that is in the browser window. This will determine where the problem is.
You can also try to manually enter the preview link into the browser to see if that works.