Você está usando tabelas InnoDB ou tabelas MyISAM? O MySQL não suporta transações em tabelas MyISAM (mas não lhe dará um erro se você tentar usá-las). Além disso, certifique-se de que seu nível de isolamento de transação esteja definido adequadamente, deve ser SERIALIZABLE, que não é o padrão para o MySQL.

Este artigo tem um bom exemplo que explica o impacto dos diferentes níveis de isolamento usando um exemplo muito semelhante ao seu.