On playing a bit more with this, it seems to happen a lot on 2G connections and far less on 3G. So I'm guessing the download times out too fast and/or doesn't do a retry?
I wonder what changed in this department, as I could (in the past) drive around using a 2G connection and the downloads worked - sometimes a tile took a bit longer, maybe those are the tiles that now fail. I also tried to move the map enough to make the failed tile drop from the drawing cache, but that trick also fails. If there's anything to try just let me know.