not always... i had a load of lego batman achievements glitch on me. i cleared cache and loaded up my save and most of the achievements popped. so maybe have a look see at that. if not then i feel you will have to replay.
i have also heard of some problems where people have had randoms join on this game and have not got storyline achievements so set game to private.