I got the Samsung 32GB off of newegg. The 16GB that works fine I got off of Amazon. All my crap would fit on a 16GB, but I like the idea of having room to expand, or in case I want to load up a movie or something. I don't have any other problems with my dstwo - NDS games play fine, and all other emulators seem to run as expected. That's why I was so confused initially, because the microsd didn't seem like a likely culprit to me since everything other than nesDS works just fine. So in any event, I'm off to try redoing my Samsung (since I don't have a spare 32GB or 16GB at the moment), hoping that if I reformat it and recopy all of the data, perhaps it will work. But now this thread can serve to answer the question of the "device failed" message. I know I'm not the first as I did see it on another forum at one point, but no one ever pinpointed what the solution was. I'll have to keep an eye out for a good deal on a Sandisk 32GB. It's so hard to know what's good and what's crap these days.
In summary, if nesDS says "device failed" check your microsd!