App and photo editor
Just need something pointy, like an unfolded paper clip. If you look at the sim holder at the top of the phone, you'll see a little hole. Stick the paper clip in there; the sim card holder will pop right out.
The iPhone came with an "official" sim card remover, but it's easy for people not to see. If you still have your box, it's probably in there.
If after taking it out and putting it back in you still get the message sometimes, then AT&T will probably give you a new sim card. It happened to me.