I never realized I have this problem since it's been a week since I installed B2E and started posting almost everything in Korean.
I initially thought that I might have had some charset conflict between B2E settings and MySQL database. However, I checked and the default character set for my database IS utf-8. and the I had set the default locale on my blog as English (US) utf8.
English search terms work all fine, but not Korean. What might cause this problem? Thanks for your suggestions in advance.