There are 2 alternatives (you may suggest more to us via the forum):
--------------
Solution 1:
--------------
-- it will work, but the menu titles, and category titles will not be translated
-- you could use Falang to translate the menu items and category titles
--------------
Solution 2:
--------------
-- NOTE: you can still use (and you should use) item associations (of translations), inside the item form, just the menu item will have higher precedence
-- NOTE: All other items of your site that do not have menu item, will be switchable because they have (translation) associations
ALSO please read this FAQ article:
Solving problems with language switching