I had what I think was a similar problem. I was able to solve it by updating my .htaccess with all of the auto-generated mod_rewrite rules on the Options page. When I originally set up my blog, I had accidentally copied only some of the rules. The ones that handle paging are nearer the end.
Did you try my instructions for installing WordPress at Dreamhost?
A common problem that people run into is unzipping the files on a Windows PC and then FTP’ing them to their server in binary mode rather than ASCII mode. This results in end of line characters getting mangled.
If your FTP program doesn’t automatically detect that a .PHP file should be transferred in ASCII mode, that could be your problem.
