Just a pure guess, but try formating the memory card in camera or try a different card. Definitely something scrambled there and it would nice if it was your card rather than your camera.
Agreed. Always blame the card first, since it's the cheapest fix.
I'd suggest trying a totally different card first. If you have no issues with the new card, take the old one and format it in your PC; but do NOT use the default "Quick Format" option. Clear that check-box and *fully* reformat the card (this will take a few minutes). Once that's done, format the card in the camera and check for joy.
The difference between formatting on the PC and formatting in-camera is that formatting on the PC wipes down and re-formats the file structure on the memory card; formatting in-camera simply re-writes the camera's folder-structure and those are two very different things. Your possibly "rogue" card needs a thorough overhauling, not just a tune-up and the only way to get that is by formatting it fully on your PC.
And, since I can hear you asking, the "Quick Format" option just erases the card's MFT, or "Master File Table", it does not really "format" the card at all, to my way of thinking; it just removes all references to the data so it LOOKS like the card has been wiped.
Good luck!
...