What happens if you turn off your category cache?
I am seeing no issue with this I unassigned one of my albums to a category and assigned an album to the members pics cats here on my little site and no issues see it shows 16 pics yet only 2 pics in that cat and the one album so the counts are right. If I take away the album it shows 2 pics as the count
http://www.reeftalk.com/gallery/index.php