Hi, I think I found the issue.
I also like the Polylang module and I also ran into 404 errors when using %postname% pretty permalinks. Because I did not find a solution to this on Internet, just a couple of similar reports, I had to sit down and debuge the module myself and I think I found it.
The issue is caused by rewrite rules added for language category, tag = "language_rewrite_rules".
Even though they ARE processed (removed) by the Polylang module (polylang.php, function rewrite_rules, lines 371-372:
if (($current_filter = current_filter()) == 'language_rewrite_rules') return array();), this processing is too late and it is not executed when the language-related rewrite rules are being created (wp-includes/rewrite.php, function rewrite_rules, line 1580:
$rules = apply_filters($permastructname . '_rewrite_rules', $rules);).
This is because the Polylang prepare_rewrite_rules() function that actually adds the filter, is called too late (Polylang constructor, line 88,
add_action('wp_loaded', array(&$this, 'prepare_rewrite_rules'), 20);)
So my suggested quick fix is to move the add_filter("language_rewrite_rules") to the end of the init method (Polylang::init(), line 335: add this line:
add_filter('language_rewrite_rules', array(&$this, 'rewrite_rules'));
Then redundant adding in prepare_rewrite_rules() can be removed, so the enumeration on line 359 can be changed to:
foreach ($types as $type)
if ($type != 'language')
add_filter($type . '_rewrite_rules', array(&$this, 'rewrite_rules'));
Works for me.