I'll add my voice to the chorus here - I ordered a nano sim from EG and picked it up at the K Books store in ICN. The directions they give to K Books on their website are accurate; I had no trouble finding the (surprisingly small) store which is open from 0700 to 2000. To get to the store, walk out of the baggage hall then immediately turn right. The store will be there on your right.

In the store I showed the guy my confirmation email but he asked for my passport. Armed with passport number he was able to pull up my order and he handed over the sim. In it went into the iPhone and after a quick reboot, all was well. I got a strong signal immediately and it never wavered.