I was given the partial solution by Dude, Kriesi and Amir. If you use Display 3 by 1 theme (latest version 2.x) then you can stop using the theme's menu manager and start using the wp menu manager. The latter one can be translated easily. This fixes the top navigation and the sidebar menu. Remaining elements to translate are the the 3 boxes in the mainpage and the footer. I found a solution for the 3 html boxes: instead of using html you can easily define to show a post. So, you just have two create 3 different posts with categories main1, main2 and main3 (you cannot choose a specific post to appear so you need to make them appear by category). This can be translated as well.
Almost there, except that there is no way of translating the link categories and links in the footer (no solution yet).
Kriesi and Amir are working together so that new theme's will be fully compatible with WPML and may even update some old themes to make them WPML compliant.
Thanks Dude for inquiring about this and giving the solution. If you have any thoughts regarding the footer, please let me know.