Lately I've been reading some of John Hawkins' A Performance Theory of Order and Constituency, which puts forwards some very appealing ideas about how to predict the relative frequency of different word orders (both cross-linguistically and within a language) by quantifying how easy they are for humans to parse. (For example, he derives such phenomena as Heavy-NP shift, the relativization hierarchy, and even the relative frequency of the six possible basic word orders SVO/SOV, VSO, etc.) Parsing issues certainly severely affect the grammaticality of sentences, as people who follow titles posts Language Log authors write have know.
I tried out a similar example in Japanese on a friend - going by the grammar books, one would expect "John said Mary thinks Bill came" to be translated as "Jon-wa Merii-ga Biru-ga kita to omou to itta", with three successive subjects followed by three successive objects. She unhesitatingly went for, as I recall, "Biru-ga kita to Merii-ga omou to Jon-ga itta" - moving the subjects to the "wrong" places to make the sentence processable - and said that the three-successive-subject one was "difficult". I can't think of any Arabic parallels offhand - postverbal objects and resumptive pronouns in relative clauses together stop most of the obvious possibilities - and Sylheti turns out to rather cleverly block almost (not quite) all possible ways in which problematic center-embedding might emerge. So my question to you is: in your language, can you think of similar examples of incomprehensible yet nominally grammatical sentences?