Ok, this problem is around since the WP2.0 release candidates.
Some people say that this might be related to the earlier version of Spam Karma for WP 1.5.
I found some help
here – http://wordpress.org/support/topic/52716?replies=10
and
here – http://comox.textdrive.com/pipermail/wp-hackers/2005-December/003592.html
Since I upgraded to WP2.0, my comments count is not working at all.
At first I was blaming the theme, but I checked the code, uploaded the whole theme again and nothing happened.
Could this be some weird server setting?