There is a saying that languages are best learned "under the pillow". This means that those married to a Korean person or dating a Korean person are more likely to learn Korean than anyone else.
No matter what language one learns and how they learn it, it is technically impossible to:
-Get rid of their mother tongue's accent or intonation
-Adapt to the second language's body language
-Adapt to the conversation etiquette of the language
-Refrain from translating idioms or phrases which exist in one's native language
-Speak with minor grammar mistakes
This, no matter how long you learn a language and how frequently you practice it. I hear people here and there asking whether it is possible one day to speak Korean like Koreans, but, for complicated scientific reasons which have something to do with how the human brain functions and the like, it is therefore impossible to reach such a level.
Korean instructors often complain about the quality of their students' Korean and insist that students should speak Korean like native speakers. Had they listened carefully in their linguistics class, taken a linguistics class or perhaps even read a serious book dealing with second language acquisition, they would not make such complaints about students.
Why do Koreans have trouble understanding foreigners when they speak Korean? First of all, Koreans get very little exposure to foreigners speaking Korean. They do listen to people like Ida Daussy or watch the global show on KBS, a show where foreigners speak Korean. But such foreigners speak Korean in front of a camera and have what is called the "observer's paradox": people tend to speak more carefully when they are facing by a camera, being recorded or speaking in public. Also, such shows tend to put subtitles and illustrations when foreigners talk to clarify what they are saying on television.
Another reason why Koreans do not understand foreigners speaking in Korean is that phonetically Korean is very different from other languages. Korean has lots of consonants and vowels, but unlike many other languages, it has very short syllables. While a word like problem can be understood when pronounced "prablem", "priblem" or "prublem", in Korean, words like 간장 "kanjang" (soy sauce), 긴장 "kinjang" (nervousness) or 건장 "keonjang"(sturdiness) or even 곤장 "konjang" (a stick) all have different meanings. This means that if you mispronounce that one vowel or consonant in Korean the word is likely to have a different meaning and you will not be understood.
I would add that Korean people only trust people who belong to their group (school, company, family, church etc.) and therefore unless belonging to a group it is very difficult for foreigners to make friends who are native speakers. They can of course make Korean friends if they attend a Korean school or company, but most foreigners do not have such opportunities. And even when working for companies or attending schools, very few conversations involve academic topics or other "serious" topics, as most conversations are centered around food, personal issues and gossip. It is therefore very difficult for foreigners to be able to converse fluently about "serious" topics.
Finally, foreigners face the reality that many Koreans working for companies are "supposed" to be bilingual. That is, these days, Korean companies only hire people who performed well at standardized English tests. Therefore, Koreans will feel obliged to speak English when they meet a foreigner, or will remain silent rather than speak Korean with foreigners. That because accepting to speak Korean with a foreigner means admitting that they did not perform well at English standardized tests which got them the job in the first place.
Institutes teaching Korean often expect students to read Korean newspapers and watch the news on Korean television. However, foreigners find little use in reading such newspapers because a large number of Chinese and English newspapers are in circulation, and because foreigners see very little use in watching the news in Korea, since they have no one to discuss the news with.
Perhaps a realistic approach to learning Korean is to expect to have decent conversation with Koreans. As Korean companies seldom ask foreigners to get tasks done in Korean, and rarely hire foreigners in positions where they have to use Korean, though this might soon change.