I had the very same problem. The reason was, that I first edited my .htaccess manually and later let WordPress edit it. That resulted in double mod_rewrite rules, as WordPress adds begin and end comments to it’s automatically written edits, but not to the generated code for manual copy&paste edits.
Just remove any double rewrite-rules and keep those with the WordPress comments around.
I suggest WordPress should also generate the comments for the copy&paste code to avoid such problems.