Noisy sensor on a prototyping board
The problem was a combination of an almost empty battery and a bad board layout. The ground of the Bluetooth module went to the the battery via the microprocessor which uses 20 times the current. Rerouting this line (and vcc) away from the microprocessor straight to the power regulator removed a lot of noise, further replacing the battery made it work great wireless. 

However when using the 5V USB as source (connected to the microprocessor) there was still a lot of noise, this was solved by temporarily attaching a capacitor (~1000 uF) over the Bluetooth's  vcc and gnd.