Ensure that your SD card (It should be and SDHC for capacities above 4GB up to 32GB for compatibility) does not have its slide tab on the wrong setting. If that's not the issue, it may be a formatting issue. Nintendo recommends using the SD Association's SD Memory Card Formatter for SD cards to be used with the 3DS product series. The software can be found here. Nintendo also mentions that you should select Overwrite format when formatting the card. Give it a shot.
If that more conventional solution does not work, there are some who solve this kind of problem by taping over the slide tab, which apparently prevents the SD card from being unintentionally locked when inserted. If this doesn't work, it's worth noting that there's a small mechanism in the card slot that determines whether or not the card inserted is write protected or not that may be bent out of place, thus resulting in the console itself seeing any card inserted as being that way. The fix for that is detailed here in another user's answer to a similar issue. In your case, you mention that the 4GB card is still read normally, so this may not be relevant to your issue, or your new card may have some slight variances in tolerancing if the solution is relevant.
Hope this helps.
EDIT: This is a link to another formatter that I've found recommended. This is a link to the third answer that I mention in my comment response below. Please check the iFixit link in my initial answer again, as I previously only linked to the question as opposed to the relevant solution involving the mechanism of the card reader.
crwdns2934105:0crwdne2934105:0
crwdns2934113:0crwdne2934113:0
crwdns2915270:0crwdne2915270:0
crwdns2889612:0crwdne2889612:0
2