Os voy a poner la solución "definitiva" para ubuntu 9.04, llevo 2 horas probando y ya he dado con ello.
El problema está es que la Magic en fastboot y en no fastboot no tienen el mismo idProduct, en modo normal es 0c02 y en modo fastboot 0fff
Así que editamos el fichero /etc/udev/rules.d/51.android.rules y le ponemos
SUBSYSTEMS=="usb", ATTRS{idVendor}=="0bb4", ATTRS{idProduct}=="0c02", MODE="0666", OWNER="owner"
SUBSYSTEMS=="usb", ATTRS{idVendor}=="0bb4", ATTRS{idProduct}=="0fff", MODE="0666", OWNER="owner"
Y reiniciamos el ordenador.
Este fichero tiene que tener los permisos que se indican en otros posts.
sudo chmod a+rx /etc/udev/rules.d/51-android.rules
Sobre todo acordaros de sustituir el owner entrecomillado por vuestro nombre de usuario.