"Are you formating the SD card with your computer? Don't. Get a brand new high quality SD card from a good retailer.
In the menu select Clear all settings."
If your card is over 32GB, then the Camera may not have the smarts to peform a low-level format on it. You would be forced to use a computer to initialize the card with Windows FAT32 formatting. Once the low-level format is done, you would still need to perform a quick format in the camera to initialize folder names. Also, only use full-size cards, and stay away from mini-cards with adapters.