I had the same problem but I managed to fix it and get all of my pieces back, good as new, without waiting for a new piece to arrive via Spotpass as many people have suggested on various sites.
It involves digging around in the file folders on the SD card, so be careful and pay attention to what folder you are in. You don't want to mess up your data, especially if you have downloaded games on your card.
First open the "Nintendo 3DS" folder. You will usually see two folders, one called "Private" and one with a long string of numbers and letters. Open the long-string one. Now you will see another folder with a different long string of numbers and letters. Open it. Now you should see three folders, "bds", "extdata", and "title". As far as I know, "title" is where your downloaded games are kept, so don't touch that one. Open "extdata". Now you'll see a folder called "00000000". Open it. Here you will have several folders that have names 8 numbers long, starting with 0s. Copy all of those folders, plug in your new SD card, and paste them into the same folder location. Make sure you copy and replace. I tried copying over only the missing data, but that didn't work. You have to replace every file (within "extdata">"00000000", not elsewhere. Again, don't touch the "title" folder) with the old version from your previous SD card in order to get your puzzle pieces back. Copy&pasting those folders, clicking "merge folders" when prompted, and clicking "copy and replace" when prompted is what solved this problem for me.
Good luck to everyone who encounters this problem in the future, and I hope this works for you too!