I play on PS3. I am 1st Prestige Level 80 and I am unable to complete some challenges still (I have done these challenges, but the challenges say I have not completed them). I'm able to look at every challenge. When I go to a challenge, sometimes it will have 2-Different-Locks, 1 of the 2-Locks, or No-Locks under where it tells you how to complete the challenge. The Locks are on random challenges throughout my Barracks except my "Prestige Challenges". There is this other glitch that has been happening to me, I have been promoted to 1st-Prestige_Level_80 about 4 times randomly while in different ranked multiplayer matches. Is this why some of my challenges are locked and I am unable to complete them? I asked one of my friends if some of his challenges are randomly locked too, and he said yes. Can anyone tell me why some of my challenges are like this and/or how to fix this problem?
The lock icons indicate that when you complete that challenge, you'll unlock a new title or emblem. There's a "square" lock which indicates an emblem, and a "rectangular" lock which indicates a new title. It does not indicate a locked challenge. (I believe challenges you can't complete due to level or a missing unlock are grayed out instead)
You should be able to complete any challenge by the time you reach the 80th level of first prestige. Some of the pointstreak reward challenges require that those pointstreaks be unlocked in the relevant pointstreak menu. Note that if you're already at the max level, the only thing you can do is unlock the title/emblem, as gaining more XP means nothing at that point.
If you aren't making progress towards a challenge although you're sure you're doing it properly, this sounds like a bug. Also, you should only be able to level up to level 80 once per prestige. Technically, you have to get to level 81 in order to prestige again, but 4 times seems a bit much.
You may want to post your issue on the Technical Support forum of the Modern Warfare 3 forums. If there's an issue that requires the MW3 developers or community managers to get involved, that's the best place to post.