Depois de muita pesquisa, encontrei uma solução. Como foi muito difícil resolvê-lo, aqui está a resposta, caso alguém encontre o mesmo bug do Black Mesa no Ubuntu.
Basta renomear o arquivo libstdc ++. so.6 para .old e o jogo será executado corretamente.