I am developing a prototype of a distance sensing device using the Pololu Sharp GP2Y0A60SZLF distance sensor, following the instructions here:

http://www.instructables.com/id/How-to-setup-a-Pololu-Carrier-with-Sharp-GP2Y0A60S/

I am following the instructions, but instead of connecting VCC (sensor) to 5V (tinyduino), I am connecting VCC (sensor) to VCC (tinyduino). I have tried connecting it to 5V on the tinyduino, and the sensor then reads always 0.

The sensor is reading, but the values are not properly distributed (e.g. I have high values at a short distance, medium values at a medium distance and again high values at a higher distance).

Any recommendations?

VCC to VCC is correct. The sensor seems to be good for 3V to 5V as well, and otherwise the connection is simple- how short is 'short distance'? This type of sensor will usually give inconsistent values below the minimum distance specified, which I believe is 10cm for the Sharp sensors.