It turns out that fiddler crabs *aren't* fully aquatic. Without air, they drown. I know, the fish store told me they were fully aquatic too. They need to surface, and if they're kept in a fully aquatic environment, they'll just die out, and your other fish will eat him, which is why he's not there anymore.
I found that out the hard way too.