The problem with XII was one of expectation. Fans were let down by the smaller roster and the immensely simplified system after XI. So much was taken out of the game from XI - leader DMs and tagging, to name a few. Compared to almost every other KoF, XII is very simple which is why I think it's a good place to start. The gameplay is smooth, the fighting is fun and the clash system is very well done.
Another reason for the hate is the online. The PS3 version got an online patch which improved performance but it's still not great. You'll need to have your PS3 wired with ports forwarded in order to have any sort of decent connection. Add me on PSN (nilcam) when you get. I'm on almost daily.