Eu finalmente resolvi o problema no que parece ser uma maneira ridiculamente simples. Já vi muitas postagens sobre esse problema, mas a única solução que encontrei foi uma que estava um pouco oculta em uma postagem do stackoverflow . Acontece que o problema pode ser resolvido no momento da conexão (o que faz sentido):
mysql_connect(HOST,USER,PASS,false,128);
A resposta está bem ali na página de manual , acontece.
A única coisa que eu ainda não entendo é por que isso é necessário na minha nova instalação do Ubuntu, mas nunca foi um problema em nenhum outro sistema, Ubuntu ou CentOS.
Devo também acrescentar que o método acima é provavelmente mais portátil do que outros métodos, já que você está configurando o tipo de conexão no código em vez de em um arquivo de configuração.