Relativamente à origem do vocábulo "Tejo" (de que "tejuelo" é apenas um diminutivo) diz-nos o "Diccionario crítico etimológico castellano e hispánico", de J. Corominas e J. A. Pascual, que este vocábulo provém de "techo", palavra castelhana que se originou no Latim "tectum" (coberto, tapado). Há algumas associações a uma árvore conífera, e também ao facto de em Cuba "tejo" designar um jogo de rapazes em que estes jogavam com botões e um pedaço de ladrilho.

Corominas não é mais específico, nem os meus conhecimentos de castelhano permitem uma resposta mais completa.

Quanto à segunda parte da questão, sobre a designação usada pelos habitantes da Península Ibérica da época medieval para o nosso tijolo, a única coisa que consegui apurar é que no século XIV havia pelo menos quatro formas: tiello, teiolo, tegelo (esta surge na "Crónica Geral de Espanha de 1344") e tigello. Este último vocábulo, segundo José Pedro Machado, também designava loiça de barro.

Espero, com isto, ter esclarecido um pouco o nosso consulente.