It's only happened to me when I have had a duplicate contact entry with the same number, usually arising from syncs. Once merged, it sorted itself out and the message app shows the name.