Bem, isso realmente soa como um erro Permission . Você verificou os executáveis que você está tentando executar?
ls -l /usr/lib/skype/skype
Isso deve gerar as permissões do arquivo (Read, Write, eXecute), respectivamente para o usuário, o grupo ao qual ele pertence e também para os outros usuários.
Como você está recebendo esse erro mais de uma vez, isso parece mais um problema de grupo. Você pode, por algum motivo, não ser membro de um grupo obrigatório. Para dizer de quais grupos você faz parte, você pode usar o comando groups
.
Claro, isso é apenas uma hipótese.