Resumo
A resposta é uma só: não devemos usar funções da extensão "mysql" pelo seu desenvolvimento ter sido descontinuado; a extensão se tornou obsoleta, ou seja, código que utilize essas funções não irá funcionar em futuras versões do PHP.
Detalhes
Um usuário do site Stack Overflow em inglês escreveu:
There is no security problem with library itself but rather with library users (não há problemas de segurança com a biblioteca em si, mas sim com os usuários da biblioteca).
A votação para descontinuar (deprecate) ou não, resultou em 25 votos a favor e 12 votos contra. Foi uma boa maioria, mas não foi uma decisão unânime. Veja a fonte oficial.
Nessa mesma fonte, outro desenvolvedor escreveu:
The extension is not broken. The problem is the bad usage. It can be used safely, and good developers have been doing so for ages (A extensão não tem defeitos. O problema é a má utilização. Ela pode ser usada com segurança, e bons desenvolvedores têm feito isso há anos).
A citação abaixo, também desse mesmo documento oficial, aponta para as verdadeiras razões para descontinuar a extensão:
ext/mysql is hard to maintain code. It is not getting new features.
Keeping it up to date for working with new versions of libmysql or
mysqlnd versions is work, we probably could spend that time better.
(A extensão mysql contém código de difícil manutenção. Não está
recebendo novas "features". Mantê-la atualizada para funcionar com
novas versões de libmysqld e mysqlnd é trabalhoso; nós poderíamos
estar usando melhor esse tempo.)
Em outras palavras: "Para que ter um trabalhão para manter esse código velho?" - pois na medida em que novas versões do MySQL (e suas "client libs") são lançadas, a extensão precisa ser atualizada...
...e, além disso, já existem as extensões mysqli (mais moderna) e a alternativa PDO... então... para que continuar mantendo? Vamos descontinuar? Aí, 25 votaram "sim", 12 votaram "não", e a decisão foi tomada.
Comentário Pessoal
Quando eu comecei com PHP não existia a extensão PDO. Eu usava a extensão "mysql", como a maioria, até que trabalhei num projeto usando "mysqli" e tomei conhecimento das vantagens, e sempre preferi a mesma desde então.
Logo depois, escrevi um par de classes que extendem as originais da extensão mysqli, e as utilizo até hoje em PHP puro, ou seja, quando não estou usando um framework como o Laravel, com seu "Fluent" e seu "Eloquent", o Symfony com "Doctrine", etc...
Para mim, acostumado até aos detalhezinhos de preparar cláusulas "LIKE" à prova de ataque, a "caixa preta" desses "prepared statements", "Active Record" ou "ORM" era vista com desconfiança. Essa fase passou, e hoje sou fã do Eloquent que vem com o Laravel 4...
Adendo
Após publicar toda a resposta acima, senti necessidade de frisar a importância do fator "not getting new features" na decisão por descontinuar a extensão. Quer dizer: apesar dela ser a mais rápida (melhor performance) na execução das tarefas simples, a ela faltam todo o leque de funcionalidades que as extensões alternativas (mysqli e PDO) contêm (transactions, suporte a SSL, etc) - ponto que foi destacado em outras respostas aqui.