Have your tried formatting the card with larger allocation tables? Hook it up to a card reader and format it on your PC like so -
format <vol:> /a:64k
This has a huge affect on the SD cards, maybe it will help in your case too. You can try 128K I think too. I've been using Transcend SD cards with good success. As long as you didn't get it off ebay from China or something, you should be good.