It's always difficult to get people to play something they don't want to, and it gets worse if you push it too hard. If people originally do not care for KOF, usually the harder you push it the more obstinate they become. Especially true if they already had a fighting game in mind (MVC, Tekken, VF and whatnot). One of the chief complaint would be that "I don't know how to play that game" or "This game suck ass, my game is better". I thought it's best NOT to contradict them on this.
Although, people will play something new if there are alot of other NEW people playing as well. So it wouldn't alienate them from the crowd, humans being social creatures and so forth...because usually people skip KOF because they're unsure whether it is worth their time. "Should I try this new KOF thing? I'm a noob and will get my ass trashed or should I just stick to SF4, which I am at least moderately awesome?" People likes to win after all.
My advice?...start small and non-threatening, and let them win most of the time.