I think this problem comes up because of UTF-8 support in Samba. I had a similar problem with a Linkstation running Debian Lenny. Once Samba was upgraded it worked fine:
I have a NetGear Stora working fine with WiiMC . Funny…I started using WiiMC because of the lack of support for NAS devices from PlayOn TV . My Wii was already softmodded so I jumped onto WiiMC and VLC Shares to play my stored videos on the Wii .