It was often said of Boycott by the WI team of the 70s and 80's that although they could see he was a great defensive player and clearly scored lots of runs, his style of play didn't often result in wins for the team off his own bat. They perceived him as a selfish player, not able to adjust to the situation of the game very often, and just stuck to what he knew which was defensive play, high price on his wicket, etc. I've read where they've said this was why they didn't respect him as an opponent as much as they did others who were slightly less successful against them.
I get the feeling that had Kallis been playing in that era, he would have been thought of similarly. In Tests, how often do we see a match-winning knock by Kallis where his knock was the difference? Pretty rarely. I think that's why he's not thought of as highly as many of his peers. Obviously a player who knows his game very, very well and is a master at doing it but he's not really a player who strikes fear into opposition hearts. They know they'll struggle to get him out, etc. but he's not a player who you'd be thinking "If we don't knock him over early, we're done-for.". Players such as Sachin, Lara (especially), Ponting, Gilchrist, etc, don't just score many runs themselves; they 'take' others with them and their play inspires others in the team to form match-winning partnerships or to rip out some quick wickets before stumps. Kallis always seems to bat 'alone', if that makes any sense. And one can't under-estimate the effect on a team of someone who does something extraordinary.
Case in point, Freddie's knock at Edgbaston. He didn't get a ton that day but it is universally considered an incredible knock, not for how many runs he scored or even for the way he did it with all the sixes but for what it did for the team. Suddenly guys like Simon Jones found someone to get behind and play well above his weight just to support Freddie. Freddie then took THE crucial wickets and England won. He didn't take a 5-fer but he didn't
need to; the wickets he took and what it did for the team because of WHEN he took them did all of the damage. Its why, even though Freddie will likely not be statistically in the same league as other great all-rounders by career-end (he had too poor a start to recover, really), he'll still be remembered as one of the best. Another one who's rapidly heading into the 'match-winning' category is Mohammed Yousuf; and it's because of how many games he wins Pakistan, not because of how many runs he scores.
Another example; Gilchrist this year against Bangladesh. Yes it 'only Bangladesh' but to that point, they were all over the Aussies. They'd batted really, really well with awesome speed and spirit in their first dig to get 400-odd and then their spinners made a mess of the Aussie top-order. They were playing in a dream and looked like they'd forgotten that they were supposed to be the worst team in Test cricket. Gichrist's knock, by it's sheer power and strength of will, reminded Bangladesh of their place in many ways. Suddenly they were snapped back to reality. Had someone else played a steadier knock to get the Aussies out of trouble, Bangladesh would probably have still been playing in the dream and batted better in their second dig (we can never know, of course). As it was, they were totally demoralised, reminded of where they stood in the world cricket pecking-order and played accordingly, scoring 148 in their second dig, and subsequent win for the Aussies followed. The next Test, they were annihilated and a tail-ender scored a double ton. Again, back to reality and I think a large chunk of that can be traced back to Gilchrist's knock.
http://www.cricinfo.com/db/ARCHIVE/2005-06/AUS_IN_BDESH/SCORECARDS/AUS_BDESH_T1_09-13APR2006.html
That's the difference between Kallis and the guys who people can never quite rate as highly no matter how many runs he scored. Players like Lara, Sachin, etc. Someone brought up Ken Barrington and that's a pretty fair comparison. Lots of runs, outstanding average but questions will always be asked as far as how many of those runs were important to his team.