Our family uses T-Mobile; we used our phones in Seoul earlier this year, as you can read in past threads (Cellphone Plan Recommendations, S. Korea Prepaid 3G Data + Voice). I'm sure you can find others by searching.

I'd suggest that you make sure the carrier settings are updated on your phone before you go, and consider renting the Olleh Egg or some equivalent. You pick it up at the airport and return it later to the same place.