When I run
adb shell, I get the following error
$> adb shell * daemon not running; starting now at tcp:5037 * daemon started successfully error: insufficient permissions for device: user in plugdev group; are your udev rules wrong? See [http://developer.android.com/tools/device.html] for more information
The connection gets thus rejected without me getting any prompt on the phone's side. I have enabled the "USB debugging" option on the phone, which when connected correctly says "USB debugging connected".