если ярлыки "не работают", то вариант один - запускать в терминале и смотреть на что ругается.
Чтобы избежать лишних телодвижений, неплохо бы сначала:
1. Окончательно убедиться, что партнерские репозитории подключены
2. Сделать последовательно
sudo apt-get update
sudo apt-get upgrade
3. Убедиться, что скайп все таки не работает
4. Запускать скайп в терминале, чтобы понять - чего ему не хватает. Команда для запуска вероятно skype