Have you ran a scan database? You sure you did not upload an old file or break it with a hack?
I have tested pretty darn good and it works fine. If I assign an album to a category the count on index shows correct.
example
Here is my index look at member pics see the photo count 20
http://www.reeftalk.com/gallery/index.php
Now view the cat and you see 4 pics but on index it had count of 20
http://www.reeftalk.com/gallery/showgallery.php/cat/508
Thats because I have a personal family pics of 16 in a private album