Stai usando tabelle InnoDB o tabelle MyISAM? MySQL non supporta le transazioni sulle tabelle MyISAM (ma non ti darà un errore se provi a usarle). Inoltre, assicurati che il livello di isolamento della transazione sia impostato in modo appropriato, dovrebbe essere SERIALIZABLE che non è l'impostazione predefinita per MySQL.
Questo articolo ha un buon esempio che spiega l'impatto dei diversi livelli di isolamento utilizzando un esempio molto simile al tuo.
