I could give you a few suggestions. If you want to build it in the skin, you could use the TEXT skin object and localize the labels in resx files.

Can't you have two different navigation objects in your skin? I never tried that, but I bet that would work

Then, there is no reason why the links dhould be made in a skin object. You could easily implement that in a module and use any module localization option.

The use of the links skin object has the advantage that the object will change in line with navigation menu if you would change the navigation structure.

If you use a TEXT skin object, you would not have that advantage, neither would you if you replace the skin object by a module. But for what I see, I do not think you would want to change the navigation system often.

I think the easiest way to go would be to replace the skin object by a module.

So, indeed, if you use another option, you might have to change the bottom links as well. However, if you select to "copy to all pages" in the module settings, you would have to do that on only one page to see the changes reflected on all pages. To achieve that, you would have to replace the skin object by a content pane and then build two links modules, one for each language. You can probably use many of the css style elements of the skin object.

But the important aspect is the user experience: you can create the same effect as you used to have: the bottom links in the language of the visitor

Look up the account taxivantha in Cambodia in Skype. Invite me and refer in the invitation to DSLocalizator. I could help you out.