Well, it's remarkable if these languages are related, but even so, we're talking about two languages that diverged thousands of years ago, maybe 10k years. Probably in the same ballpark as Proto-Indo-European or even older.
That is, these two languages would be about as mutually intelligible as, say, English and Albanian, or less.
I have doubts as well. "Almost" may be carrying a heavy load there. People are just really good at communicating, face to face, over difficult barriers, particularly when they share cultural underpinnings. But I don't speak any language in the family, and can only go on what they say.
