Service discovery failed exception using Bluetooth on Android

After three days I got it figured out thanks to some very helpful posts.

I had to replace:

tmp = device.createRfcommSocketToServiceRecord(MY_UUID);

with:

Method m = device.getClass().getMethod("createRfcommSocket", new Class[] {int.class});
         tmp = (BluetoothSocket) m.invoke(device, 1);

and voilà it works!