As duas frases estão correctas, mas há algumas considerações a fazer sobre a sua estrutura e aceitabilidade.
Primeiro, deve-se ter em mente que, relativamente a grupos nominais constituídos por expressões partitivas (p. ex., «parte de», «o resto de», «metade de») seguidas de substantivo ou pronome no plural, a concordância verbal faz-se ou com a expressão partitiva ou com as palavras que a completam (ver Celso Cunha e Lindley Cintra, Nova Gramática do Português Contemporâneo, 1984, pág. 496).1 Mas, no caso da frase apresentada, a concordância não é verbal, é adje{#c|}tival. Aplica-se a mesma regra?
Aplica-se, até porque a sequência «grande parte deles incompreensíveis/incompreensível à partida» é um aposto que encerra uma predicação («existe algo que é incompreensível»), podendo todo o constituinte com essa função sintáctica ser parafraseado por uma oração relativa apositiva com o verbo numa forma finita ou no gerúndio: «grande parte dos quais eram incompreensíveis/era incompreensível à partida»; «sendo grande parte deles incompreensíveis/incompreensível à partida».
Em segundo lugar, parece-me que, num aposto como o descrito, se apresenta uma situação semelhante à da concordância com particípios verbais e adjectivos predicativos. Nestes casos, João Andrade Peres e Telmo Móia falam de uma preferência dos falantes pela concordância com o nome mais encaixado, isto é, o substantivo que complementa a expressão partitiva (Áreas Críticas da Língua Portuguesa, 2.ª edição, 2003, pág. 480). Isto significa que, comparando as frases a seguir, (2) seja considerada melhor que (1) (exemplos de Peres e Móia, op. cit.):
(1) «Um terço dos professores foi convocado para vigiar a prova.»
(2) «Um terço dos professores foram convocados para vigiar a prova.»
Voltando aos exemplos em discussão, já vimos que a palavra que complementa a expressão também pode ser um pronome. Sendo assim, uma vez que a questão é saber com que elemento concorda o adjectivo incompreensível — se com «grande parte», no singular, se com o pronome «eles», no plural —, direi que «grande parte deles incompreensível à partida» é gramatical, mas a alternativa, que inclui o plural «incompreensíveis», é preferível.
1 A concordância com «grande parte» é sintáctica, enquanto a concordância com «eles» é semântica (ver concordância siléptica em Concordância do verbo).
