Ok, problema solucionado. Al final, como no, una tonteria: Cuando hacía las pruebas, conectaba los pines del Arduino a unos interruptores y demás que tenía a la breadboard, y justo estaban usando los pines 13, 12 y 11, por lo que al ser compartidos con los del ICSP daba error.
Así que: Moraleja: Desconecta los pines antes de hacer upload con ICSP.
Sobre los multiplexores, la idea es que para los que sirven para entradas, notifiquen via interrupción a la CPU que hay un cambio y por lo tanto se ejecute via interrupción la lectura de los integrados, todos ellos.