Funnily enough, when I saw the 13th Warrior in the theaters, it wasn't the same version that I saw later on the DVD. There were a few scenes in it from the book that were left out of the DVD (like the scene where they test one of the warriors wounds to see if his wound is fatal by pouring a liquid over it and seeing it bubble, knowing the wound has cut into his stomach and predicting his death) or that were changed (parts of the confrontation with the Mother of the Wendol), so I can only imagine we might have seen one of the pre-reshoots versions, or an early cut of the final film sent out by accident or they continued editing the film with that result ending up on DVD.
Sadly its been so long, I can't remember all the differences (might have to ask my brother who was at the same theater showing).