Well, it could be several things.
1. It could be your hard drive. Do you have one? If not, that could be the problem
2. It could be lag in Bungie's Service Record. Sometimes their status updates take a while. Does your rank show up properly?
3. You might not be a lieutenant. You need to be a lieutenant as your overall rank, NOT an experience rank in a single playlist.
If you have a hard drive, and you're positive that lieutenant is your overall rank (on your service record), then it's most likely lag. If you're confident it IS your 360, there's a secret code to clear your cache, if you have a hard drive. Go to System and under Memory, highlight Hard Drive, then hit Y, X, X, LB, RB, X, X.
Hopefully you found a fix in this.