I just realized that "Flush tables with Read Lock" will not work when a Select query is not yet done.
What happened was there was a runaway query where it was doing a self-join and aggregating the result. The table was about 10 million rows.
When the backup script ran, it issued the flush tables first but since it saw that a select query was still running, the flush table also waited until the query finished which it never did.
In the end, the backup did not work because of the runaway query.
I'm pretty sure that I have read the previous statement in the manual before but it is interesting when an actual warning / caution from the manual actually happens in production.