I have a variant of a problem that seems to be common from other posts. I am running Linux Mint x64 and I usually have Skype running in the background (there's the little green cloud with the checkmark in my notification area). I never turn my computer off - usually I just suspend. But, when I do so, I notice that the green cloud in the notification area disappears, just as I click the 'Shut Down' option in the menu (to get to the dialog with 'Suspend'). Then, when I resume working on my computer, the notification icon doesn't reappear and when I try to start Skype again, I get the "Another Instance May Exist" message. I have been manually been killing the remaining processes and restarting, but ideally Skype would just remain open and in the notification area... anyway to make this possible?
I had a similar problem - and it even continued after a reboot.
I switched my Linux distro to Pocket Rocket Linux (same name dot com) - which works from RAM and runs faster than what I had before - and because it refreshes each boot the problem went away.
I have found that when this error is given despite there actually being no instance of skype up it's because the .lck files skype created were not deleted.
This can be fixed by, deleting ~/.Skype/yourskypename/config.lck and ~/.Skype/shared.lck. After this you have to restart your session I think (like logging out and back in, restart, et cetera) Make sure skype is actually not running before doing this by doing killall skype -s SIGKILL
In Mint [Ubuntu for dummies] it's a `dot' file in your home directory, so do a `view all' choice in Nautilus or [if you have it] open MC as sudo in a terminal..
[Edit.. I got this situation by opening Skype in a terminal, then killing the terminal rather than exiting Skype first lol]
mv ~./Skype/<SKYPEUSERNAME> ~./Skype/OLD
start Skype - all fixed
Works on Linux Mint 12.04