I have the same error since upgrading to 13.04. However, I could not solve it with the workaround in #12 (I do not even have prelink installed); also no success with purging/reinstalling everything skype-related. I am also unable to use ubuntu-bug, getting an error "This is not an official Ubuntu package. Please remove any third party package and try again". However, I straced it, maybe this helps.
** Attachment added: "skype-strace" https://bugs.launchpad.net/ubuntu/+source/skype/+bug/1002187/+attachment/3547627/+files/skype-strace -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/1002187 Title: Skype won't start (segmentation fault) To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/skype/+bug/1002187/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs