I worked in Korea for two years. Most of the teachers I knew there had their undergrad with no teaching certificate and started with no experience. If you were rejected with better qualifications than most and no explanation it may well be because of the color of your skin. Koreans have a very definite idea of what they think an English teacher should look like and as unpleasant and racist as it may be, that does not include dark skinned people. A Canadian friend of mine of Indian decent was actually told that he was not hired at a certain school because of the color of his skin.
The author of the blog "Ask a Korean" talks about this issue in Korean society, if you've any desire to read up on it: http://askakorean.blogspot.com/2007/03/ ... along.html