This seems like a very frustrating issue! By looking at your file, I was able to narrow down the possibilities. When I delete the vertices in your model’s head, there is no problem with auto-weighting the rest of his body to the armature.
Something is going on with the head, but I can’t figure out exactly what. I recommend separating the head section from the rest of the body object and weight-painting it manually.
PS. Name your bones BEFORE weight-painting or you will have to name them AND rename the vertex groups later. Also I didn’t bother auto-weighting those little pieces of armor. Those will lag your rig and they’re supposed not to bend anyway, so you’re better off parenting those manually to the bones, or vertices of the base mesh if you want to get clever.