There are two opposing factors going on here. Between Viking days and now, Iceland has remained relatively undisturbed. There was no wave of migration or foreign invasion, no major cultural upheaval, and relatively little exposure to foreign trade. I can't speak more directly as to the changes from Old Norse to modern Icelandic, or verify the truth of what is in the novel. But the language certainly had reasons to evolve slowly.
There was a major difference in the development of English, and his name was William the Conqueror. With the Norman conquest, the Germanic Old English language became heavily influenced by Norman French. Within a few hundred years, the language that emerged was very different. Here are the first lines of Beowulf in Old English. (The letters þ (thorn) and ð (eth) were used in Old English for the th sound.)
Hwæt! We Gar-Dena in gear-dagum þeod-cyninga, þrym gefrunon, hu ða æþelingas ellen fremedon!
The poem was several hundred years old by the Norman Conquest but an Englishman of 1065 could have read it as easily as we read Shakespeare today. To a modern English speaker, it might as well be in Klingon though.
Here it is in modern English:
Hark, we spear-Danes in years gone Of those clan-kings heard of their glory How the nobles did brave deeds
If you put the two side by side, (and use your imagination), you can maybe think that "gear" might be "year" (you'd be right!) and that "cyninga" had something to do with "king" (also right). But there is little to recognize as English to our eyes.
Then the Normans came. For some time after the conquest they continued to speak French, and their Anglo-Saxon subjects spoke English. Gradually however the populations mixed and so did their language. What came out is not far off from what we use today.
A knyght ther was, and that a worthy man, That fro the tyme that he first bigan To riden out, he loved chivalrie
That's from the Canterbury Tales from the late 1300s. It would have sounded different when spoken, as pronunciations tend to change a lot more than spellings over time, but you can read it.
So to go back to the original question, although a modern English speaker wouldn't recognize the speech of 1065 at all, he'd have a decent chance just a few hundred years later.
There are some regular but significant sound changes between Old Norse and Icelandic, as follows:
The -r => -ur/ -ir change in particular affects a large class of words: strong masculine nouns.
While the orthography for ON initial consonant clusters, hl-, hr-, hn-, Icelandic gets around them by eliding the second consonant, and rendering them all as /h/.
There was also a shift in vocalic pronunciations during the Middle Icelandic period, similar to what occurred in English. The stress of words has also been altered from ON.
Something else I detected back when Eyjafjallajökull erupted was that ll was being pronounced as /tl/.
In short, I'd speculate that a MI speaker would have some difficulty with spoken ON, (though I'd agree, less than a Modern English speaker with Anglo-Saxon) as with someone speaking in a heavy accent. With time and a good ear, they'd begin to recognize the differences and adjust to them.