You can see that Uhura makes many, many grammar mistakes, and doesn’t have a “Klingon” accent.
This happens to me all the time when I speak Japanese: I sound like an idiot, I use strange grammar and I have an accent. It doesn’t sound natural. I’m grateful though, because at least with Japanese, I have some speaking practice. With Korean, I have even less practice, so it sounds even worse.
As you can see in the scene above, books don’t really help. Language is fluid and unpredictable, so you have to be comfortable enough that you can adapt to the situation. Practice over study.