My menu doesn’t change with the language
Frequently, this is due to a bug in the theme (generally themes which have only one menu location). Make this test: deactivate Polylang and create two menus in your theme. Assign the second menu which you have created and check your frontend. If your theme doesn’t display the right menu, please contact the theme support and refer this post explaining the reasons and how to solve the bug.
Another frequent issue is a menu which is correct when directly accessing the page but doesn’t switch when clicking on the language switcher. More and more themes are loading the content in Ajax and thus don’t reload the menu and content common to every pages (ex footer, widgets). This Ajax feature is obviously not compatible with multilingual websites. Try disabling the Ajax feature in your theme options or contact the theme support if you don’t find such option.
I use an Artisteer generated theme and my menu does not display correctly
The Artisteer themes do not use the standard way to create navigation menus and need some modifications to be compatible with Polylang. Look at the following forum topics: