I just changed the slugs for 4 pages on my site, and since then I get a 404 when trying to visit them. When I switch to normal/ugly permalink structure it's fine, and when I switch back the problem remains. the rest of the pages with slugs that were not recently changes work fine.
I tried refreshing the permalink structure, but the problem persists.
EDIT: I just had a look in the DB, in the table wp_posts i examined the field post_name, and found out that the recently changed pages had their new slugs saved as hebrew letters in the DB, while the 'old' slugs where saved as the UTF characters that resemble the hebrew letters... for example: "%d7%a7%d7%95%d7%a4%d7%94"
In other words: - Wordpress used to store hebrew slugs in the DB like this: "%d7%a7%d7%95%d7%a4%d7%94" and it worked fine - Lately, wordpress has started storing slugs in hebrew: "קופה" and these new slugs make an error and return 404.
What could be causing WP to do that? could that be related to the fact that i recently changed hosting providers?