Last week I was an avid reader of this topic because I messed with one… no, with two SD cards and I would get the “Insert SD card” message with both, when both had worked perfectly well just a day before.
Today both work again. It wasn’t because of any of the reasons shared above. I tried everything, even waiting a minute before removing the ejected USB stick. 
I didn’t like to use Windows to solve this, or to install a freeware utility just for this, or user 3 different card readers… Too much black magic for what is just some metals and file formats playing together,
So this is what worked for me in the end:
- Make sure that the SD card is partitioned as “MBR”. Turns out there are other options that are fine for a PC but not for the Play. This information is not obvious or very visible, and it’s the problem I had in one of the cards.
- Make sure that there is only one partition. Or if you really need to have more than one, make sure that the partition that is going to be read first is the one with the Play folders. The other SD card had a small “free space” partition at the beginning, the PC would just skip it, but the Play would get stuck with it and not find the Play folders.
- With the 2 steps above completed, formatting the SD Card to FAT is the easiest step.
My mistake was to think that “logically” a SD card problem with the Windows FAT formatting would be better solved in Windows. Actually, the problem was that the Windows apps wanted to make my life easy, by hiding these important details. Then I tried the Disks app in Ubuntu (a preinstalled utility) which shows you transparently what the SD card has, and allows you to format the entire drive (and not just one partition) just as transparently.
Once I figured this out, I fixed both SD cards in the time it gets to download and copy the Play files.