Hmm... I doubt it would have been a new update. Are you sure you never cleared the consoles cache or anything like that? And doesn't the console only hold a handful of updates anyway?
I'd be more than willing to try and boost the achievement, in hopes that if there was a new update, it may have fixed the broken achievement.