Dear Dil,
A good first step would be to check what differences there are between the users who can approve and get the message, and those who can not. I recommend that you check the persons records, access groups, if they are global users, anything that could be connected, and obviously - how the approval rules are constructed. If this gives you no clue, perhaps it's a good idea to ask a proffessional to look into your database.
Since the feature works fine for some of your users, it seems like it's a setting issue.
Best regards,
HansaWorld