A lot of great advice in this thread already. I come from mostly a SF background but this problem is something that plagues a lot of people getting into FG's.
As mentioned, don't just practice on a static dummy in training. Rarely will a real opponent just stand there and let you hitconfirm into a combo.
Before working out combos (you should still try to get them into muscle memory) keep working on fundamentals. Then watch a lot of your replays and think to yourself, "What could I have done better?" When analyzing your replays look for missed opportunities where you could have started a combo. I find that when I'm in the heat of battle you miss 90% of what you'll see when you watch the replay.
All in all, keep playing!
I'm in the process of learning KoF right now and if you play on XBL you can add me. Gamertag: Yewni