Before I proceed on writing anything just have a look the following images. (snapshots)
I have one custom post type by name 'questions' just like we have 'posts/pages'. If you look at the image one, you can find that. And I found categories in that too. When I click on one of the categories in that (like Apostasy which has 1 article), I found that in categories of the questions (have a look at the image-2 for seeing that posts). Now, when I begin to edit that article (as you asked me in the question), I find 'categories on the right side as it supposed to be and it is no doubt have tick marks on the respected categories which my client needed. When I click on update. The questions are moving to the url
fatwaa.com/questions/post-title. Whereas, when you look at the categories, you found zero posts.
I then soon back posted a test article in the 'Post' Section by ticking mark the respected category then without any difficulty I'm getting that in the category. I have edited one archive and tick mark one category into that and it is working without any difficulty.
So, I think the whole problem is causing due to this 'Questions Template'.
Also on the home page whenever I go to any category it is displaying same posts again and again..
(here is the code of the home page) http://pastebin.com/5LqnwAzY