I looked at the debug log. You are storing books by extension, with "mobi" in ..../mobi and epub in ..../epub. There are 11909 epub files in the epub folder.
SD cards are usually formatted in FAT32. I think you have run into a FAT32 limit, which is 65532 entries in a single folder. A file can take multiple entries depending on its file length. You are using title - author so the file names are long. If the average file name length is 44 characters then the system cannot store any more files in that folder. This is what I think is happening to you, especially given that CC is internally reporting "no space on device" for that folder but not for the mobi folder.
That number of files in a folder will also probably be very slow.
If you follow the directions in this FAQ you will fix the no-space problem and also fix the performance problem (if you have one).
I have added a lot of books on an SD card and now downloading books takes forever. What do I do?
As for why the new SD card works, I don't know. It could be that the new card is formatted in something other than FAT32. It could be that there was "wastage" in the old folder that accumulated over time. Or something else. If it is the second then the same problem will eventually happen again.