Yesterday (16 October 2012), the problem happened again to me and I was actually happy about it as I was able to test a bit more about the solution I wrote here:
Here is an updated version of the solution.
1) Make sure you log out of the active user who has the problem. I tried by simply closing all the programs and going to the admin account but the problem was not solved. I really had to log out with the current user.
2) Log in as the admin user of the computer.
3) Delete everything in: C:\Users\user-with-the-problem\AppData\Local\Microsoft\Internet Explorer
(change "user-with-the-problem" with the username of the user having the problem, ie the user you use when you have the problem)
This may be a bit tricky. First, why Internet Explorer? You may not even use this browser. Well, it seems that Skype is using some shared folders with Internet Explorer. Then, you may not see the folder AppData. Just type it after the username of the user with the problem.
4) Log back on the user you were using and launch Skype. The problem should be solved.
If the problem is not solved, please check the original solution here: http://smallittips.blogspot.com/2012/09/how-to-solve-skype-japanese-characters.html.