(1st attached pic)
Why Does This Happen?
This error is usually due to a faulty connection between the motherboard and the SIM / MicroSD card tray. Likely it is due to a bad solder job on that connector.
Does a new SIM Tray fix it?
Extremely unlikely. Purchasing a new SIM tray will likely be wasted money. (EDIT: A new motherboard may fix the issue, and several people have had success with a new SIM tray)
How do I fix it already??
This is what you'll need:
A micro Philips-head screwdriver
A foam earplug (or something of similar texture)
Step 1: Disassemble your phone. Pull off the back cover, remove the battery and cards, then unscrew all 9 of the micro Philips screws. Then, take your fingernail and pry off the bezel from the rest of the phone, and slowly work your nail around the bezel until it pops off. (Don't force it!)
(Attached images 2, 3, and 4)
Step 2: Use your scissors or a razor blade to cut a section off of the foam earplug which is about the width of two dimes. I also cut a 1/4 segment out of mine so you don't see it sticking out when you put the bezel back together, but you don't absolutely need to do that.
(Attached images 5 & 6)
Step 3: Press down on the connector for the SIM / SD Card Tray until it "clicks" into place. (It may not click if it is still somewhat in place) This is the connector which has a bad connection.
(Attached image 7)
Step 4: Place your piece of foam on top of the connector in a way that it is right beside but not overlapping the camera (as pictured)
(Attached image 8)
Step 5: Replace your back cover, making sure not to move the foam you just installed, press down on it in multiple locations until it pops back together all around, and screw it back down. Note: if the bezel appears to be bulging out, your foam is too thick! This won't cause any problems, but it will be a noticeable bulge on your phone.
(Attached images 9 & 10)
Step 6: Replace your back cover and enjoy! Note that if you continue to receive the error, you may need either a thicker piece of foam, or you may need to reposition the foam, or even just press down on the connector a bit more before installing the foam.
Thanks to the folks over at Android Central in the thread entitled: Galaxy S4: Major problem - SIM card not detected for info on how to fix!
After applying this fix (took me three times to get it right) I have not seen the SIM card removed error in almost two months!
Post your success stories!
EDIT: A year after I posted this, and people are still using this thread to iron out their issues. I'm glad I could start up a conversation about this problem, with many good suggestions as to possible fixes. I don't use my S4 anymore, but it makes for a great backup phone!
Anyway, I just wanted to let anybody who is looking for the answer to this problem know that my fix may or may not work for you. It worked in my case, but several commenters have noted that the problem has remained in their situation. I would like to point out a few helpful comments and possible fixes right here so you guys don't have to go searching through pages of comments to find different solutions.
Best solution by far is by @Gonemad to re-flow the solder to that connector and to the NFC chip using a heat gun. See post #98 on page 10 and Post 114 on page 12, with a guide on post 122, page 13.
A replacement motherboard may fix the issue as well, but that's assuming you're getting a new one and not a used one. With used, the replacement board may do the same thing!