Hello. Problem is serious since a friend of mine got the same problem. Game shows that Achievement has been unlocked but really hasn't. When I LOG IN to www.live.xbox.com , I can really see what has been unlocked. THIS IS NOT THE ACHIEVEMENTS BLOCKED by CHEATS. I can list u some that I or my friend haven't unlocked:

Lowest Point
Finish Him
King of QUB3D
Chain Reaction
Let Sleeping Rockstars Lie
Assassin's Greed
(we still haven't finished this game so can be more)

Again!!! We have seen message that these achievements has been unlocked, but the game somehow not sending information to LIVE & they are not really unlocked: always check on: www.live.xbox.com

ROCKSTAR fix this quick PLEASE