После обновления WP на 3.1 не открываются категории

Обновил WP и заметил, что страницы категорий и тегов перестали открываться при включённых постоянных ссылках (mod_rewrite). Пишет 404. С выключенными всё грузит.

Вот как пример. Должен открывать категорию, а открывает 404 страницу: http://e-dotu.ru/category/en-francais/

Такое независимо от темы. Все плагины отключал — так же.

Содержимое .htaccess:

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

# END WordPress

В чём может быть проблема? Хостер говорит, что с mod_rewrite всё в порядке.