The usual solutions to this is to add oneself to the dialup group, or mess around in /etc/udev/rules.d/99-arduino.rules.
None of these worked for me. However Arduino is able to program the micros fine if I run it as root, which clued me into that fact that there is some finite time between the kernel creating /dev/ttyACM0 and udev rules having effect. Specifically, udevd is a userspace daemon, and therefore necessary runs sometime after the kernel as created the relevant device node.
The problem is thus: Arduino IDE opens /dev/ttyACM0 at 1200bps and immediately closes it. This is causes the ATmega32u4 to reset itself, causing the serial port to disappear. When the bootloader runs, it presents itself as a usb-serial device, and /dev/ttyACM0 appears again. Reappearance of /dev/ttyACM0 causes the Arduino IDE to launch avrdude, which immediately tries to open /dev/ttyACM0 and fails because udev hasn't had time to process all the rules and assign the correct permissions etc.
The solution then is to introduce a delay before running avrdude, or even better, let udev let us known when it is done, which is much more robust. This can be done using
udevadm settle -t 1
Which waits for the udev to "settle", and the -t 1 specifies a maximum wait time of 1 second.
I hit upon the idea of wrapping avrdude in a shellscript and then adding the above line before avrdude, and that was when I discovered that hardware/tools/avr/bin/avrdude is already a shellscript! This made things much easier.
My Arduino IDE's avrdude script now looks like:
$ cat hardware/tools/avr/bin/avrdude #!/bin/bash udevadm settle -t 1 export LD_LIBRARY_PATH="`dirname "$0"`/../lib/" exec -a "$0" "`dirname "$0"`/avrdude_bin" "$@"
Programming of Arduino Micro and SparkFun Pro Mini is now flawless under Xubuntu 15.10.