I had the exact same problem once. My story:
I was on vacation. I was playing Star Fox Command with my brother over Download Play. I couldn't beat him, so I Soft Resetted. My DS froze. So I turned it off and back on. And... it couldn't find _DS_MENU.DAT! Mind you, this wasn't 1.12, it was the one before the first one with Download Play support.
I was able to find a PC to put the software on it again. When I did that it got corrupted so bad that no device would read it at all! I couldn't even format it on my PC
When I got back home, I returned the faulty card (Sandisk 2 GB MicroSD) to the shop. They thought it had to do with magnets too. But I got a new one.
Three weeks later, the same thing happened!
When I tried to run SD Formatter 2.0 on it it worked. Since then (about 6 months ago now) the card has worked flawlessly in my M3 Simply and M3 Real.
My advice: format with SD Formatter 2.0
Edit: btw, you can just use 1.12, it's not causing the problem. I thought that the Soft Reset caused the problem at that time, but that's probably stupid too.