What is the cheapest sensor that can detect a wall regardless of color?
Search for HC-SR04 on any shopping site. Their price starts at about 1 GBP. It appears to be the same part as at dx.com. 

They will need something to drive the transmit pin, and time the 'echo'. Most people use a microcontroller. The sensor has an input pin to trigger the transmitted signal, and an output pin which it asserts to say when it detected the echo. So the total cost needs to include an MCU.

An alternative is IR. The technique measures the brightness of light reflected from a surface. It needs some calibration, and is usually only good for about 20-30cm. Further, they can be confused or swamped by sun-light, and some types of lighting. So typically they are measured with the IR emitter on, and off, to get a difference. Usually people use a MCU. Search for 'micromouse distance sensor', and you'll find lots of information.

Silicon Labs make Si1102 Proximity Sensor IC. It uses IR. However, is autonomous, and does all of the processing itself. Its sensing distance is programmed with a couple of resistors, and it raises a digital pin when the sensing threshold is crossed. So it doesn't actually need an MCU. It is under 2 GBP from distributers, and also needs an IR emitter (which are under 0.50 GBP).