Hi, Rasmus.
I just had the same issue here. Fortunatelly I had the same code and HC-SR04 sensor working on a Arduino Uno board.
After some tests I found out the problem is the Arduino Nano built it power supply does not have enough power to sustain the HC-SR04 sensor when connected to an USB port.
It was at only 4.6V and this was causing the distance measure error.
I powered the Arduino Nano board with a 9v external battery (pin 30) and it started to work perfectly!
I hope this helps you out.
Barbado.