Dado que el hielo es una acumulacion de agua en estado solido, a lo mejor podria servirte como "sensor" unos alambres de cobre pegados a las paredes del frigorifico de forma horizontal y continua, pero de forma que si dos alambres adyacentes se tocan, se cierre un circuito.
Asi, al crearse hielo en las paredes, cortocircuitaria esos alambres y cerraria un circuito (como si fuera un interruptor). Ese circuito iria conectado a la entrada de tu PIC.
Que alguien me corrija si me he saltado algo.