Se você souber quais diretórios foram afetados, parece que você pode executar, por exemplo:
chmod -R 755 /usr/bin
-R é recursivo. Isso deve ser bom para tudo em um diretório bin . Se chmod for afetado, você poderá tentar isso ou então inicialize a caixa com um live CD e use isso.