ADB unable to connect my Nexus 7 on Ubuntu
The fact that the "Connected" message only appeared sometimes and that lsusb was unable to detect the Nexus casted a doubt on the cable.

I just tested with another cable and it works. My other cable seems to have a damaged connector.