For whoever is interested I managed to fix this as well. The solution is to convert all the INI files present in $NSISDIR\Contrib\******odernUI\Ini\ to UTF-16LE (You can do this with Notepad++). That way, WriteIniStr can detect the encoding and write a proper string that can appear no problem.
To recap, to get UMUI working with Unicode:
1) Get the SkinnedControls.dll compiled for Unicode (posted a couple of posts above)
2) Get the NSISArray.dll comiled for Unicode (thanks to afrowuk: http://www.afrowuk.co.uk/
3) DO NOT define UMUI_USE_INSTALLOPTIONSEX (At least until we get InstallOptionsEx compiled for Unicode, will work on that as well!). That means you can't use the TreeVIew in the AlternativeStartMenu page.
4) Convert all the INI files from UMUI from ANSI to UTF-16LE
I have tested this only on my Win7 machine so as usual anything can break on any other PC but at least now it's working fine.