MBAM has worked in several cases I have come across with skype-based worms like this. Your fix also works sometimes, and typically the combination of uninstalling / re-installing skype is enough to do the job. Oh, and remember to boot into safe mode when using MBAM to be most effective. MBAM is also typically most effective when used in conjuntion with another effective antivirus such as AVAST! or Kapersky.
The moral of the story here is to be smart when running things you download directly from other people. Scan it before you run it, and know the right methods and tools for removal so that you have them at your disposal if and when it comes time for you to draw on that knowledge.
kaspersky stopped it in its tracks when that came around some time ago, so when it came back i learned not to touch it.