my local electronics shop insisted that the only way of doing this was by changing the Arduino for a 5v one
Let me guess, they have one on the shelf 
passing the output from the sensor through a voltage divider
That should work, looks like it has an analog output so run that into one of the analog pins after the divider.
Rob