I just came across Tilted Twister while reading Mike Walsh’s LEGO Blog (link removed, as apparently his site has been compromised). It’s a Mindstorms NXT robot that can solve the Rubik’s Cube!
The really amazing part is that it’s built using only the parts in the stock NXT kit. Instructions are provided – I’m tempted to make one myself. (Note however that you either need to buy a special color sensor, or modify the colors of your Rubik’s Cube so that white and yellow can be distinguished by the stock light sensor.