I have been in Taiwan for 3 years and the experience has been good. I read the post from Hong Kong and although the there are a lot of similarities, there is more freedom to do extra work outside of the college/university.
Almost any college or university would hire a native English speaking Ph.D. and work them into their foreign language department. Some of the larger schools have other departments that teach in English.
A person with an MA could find 'part-time' work at a university or perhaps a high school or middle school. But I am not familiar with the K-12 systems.
When I was looking for a job, I found there are many opportunities in China too. They offer a lot of perks but the salary is so much lower that I can save more money in Taiwan even though they seldom offer the extras you get in China.
If you are interested, I would be glad to answer any questions.
jsinden@ocit.edu.tw