I've got an AT&T SIII. I had it rooted within 10 mins of leaving the strore. I've run all sorts of different SD cards, roms, apps, tweaked the cpu, etc. I've never had this problem until about 2 weeks ago. My 32GB class 10 Lexan (lexar, lexor, something) card failed. Couldn't get it to work on the phone, PC, nuthin. So I grabbed another one. It worked fine for a bit but then started giving me the "SD card removed" error but it would read on the computer and sometimes in the phone. After I formatted an class 10 Patriot 64GB SD card with the utility you get from (whatever the professional body for SD cards is) as SDXC I put it in and it wouldn't recognize it. It did work in the computer I changed it to fat32 and it would recognize it but it wouldn't let me write to it. I put my good(ish) newer 32GB card back in and it's still working the same, reads and writes, but I keep getting the same error.
I don't know if it might be connected in any way, but I'll mention it because I've seen people sometimes mentioning both but not as connected... I'm also have a hell of a time with my WiFi. It might be Cyanogenmod 10.1.2, but I figured I'd throw it out there...