As i see it, the things that make people think that kofxiii is hard to learn is A) it's not sf4 even though it may seem similar B) it's fast. When you have to constantly act quickly you need to practice, alot of things have to become second nature, you don't have time to think and then think again. Strings are generally very lenient in kofxiii, but as they are generally faster than strings in sf4, most players who are used to to those are probably thrown off. Beginners might not even be able to cope with it at first, but the thing with fast strings and inputs is that it's only "hard" for so long. If you just keep playing it all gets easier and easier. All it takes is time, and this is really the problem as alot of people simply don't want to go through the process of learning a new fighting game.
[Personal story]I have a couple of friends i play offline with, less and less sadly. We played sf4, i got bored and bought mvc3 just to get to play something else. Two of my three friends enjoyed that game with me for a couple of sessions, neither of those two actually wanted to buy it though. I wasn't really into mvc3 but i looked forward to mortal kombat so i got that. We played it and two of the three enjoyed it, the third complained about it being stiff and about all the ways it differs from sf4. No one bought it, though the possibly least likely person to do so actually sat down and practiced combos and later on i got him to buy and play ttt2 with me. Come kofxiii i actually got two of them to buy the game, we played for a few sessions and they seemed to enjoy it though not equally between them or us. One of the two practiced a bit, the other started to complain over time about me practicing too much and that it's uneven, ultimately getting to the point that we should be playing sf4 because it's more even, more fair.
Kof might still get more popular over time as people might slowly gain an interest and get a taste for the games as they get stream time and if they get popular enough, the whole "it's too difficult" thing will probably be forgotten.