Използвате ли InnoDB таблици или MyISAM таблици? MySQL не поддържа транзакции в MyISAM таблици (но няма да ви даде грешка, ако се опитате да ги използвате). Също така, уверете се, че нивото на изолация на транзакциите ви е зададено правилно, то трябва да бъде SERIALIZABLE, което не е по подразбиране за MySQL.
Тази статия има добър пример, който обяснява въздействието на различните нива на изолация, като използва пример, много подобен на вашия.