I found the solution, when you edit the menu from Appearence->Menus add the desired menu items, and afterwards edit each item with the corresponding language code before it : [:en]contact[:es]contacto and so on, but be sure to do it for each at once.
If you later edit only one menu item, that one will change correctly but the other ones will not. So everytime you edit the menu you will have to re-edit all the items.
Hope this helps you guys!
Cheers!