Therefore I tried the newest version of the Arduino software from the arduino homepage.
The package version I am using is 1:1.0.5+dfsg2-2, the other I tried was 2:1.0.5+dfsg2-4.
That is not the newest version.
I think the more recent versions of the IDE are more robust - after all they have fixed reported bugs. Try 1.6.5 or 1.6.7. The version 1.0.5 is pretty old.
I too have had "upload completed" on my Leonardo (virtually the same as the Micro) when it did no such thing.
I am using Ubuntu 14.04 and don't have any problems programming my Micro with IDE 1.6.7.
When programming you should see the Tx/Rx and yellow LEDs flicker. If not, press Reset when it starts to upload and try again.
Have you followed the instructions here? Arduino Troubleshooting.
I installed the arduino software using apt-get ...
Personally I download the IDE from this page: https://www.arduino.cc/en/Main/Software
Update
I just compiled and uploaded "Blink" with IDE 1.6.7 to my Micro on Ubuntu 14.04. This is what I saw:
Forcing reset using 1200bps open/close on port /dev/ttyACM1
PORTS {/dev/ttyACM0, /dev/ttyACM1, } / {/dev/ttyACM0, } => {}
PORTS {/dev/ttyACM0, } / {/dev/ttyACM0, /dev/ttyACM1, } => {/dev/ttyACM1, }
Found upload port: /dev/ttyACM1
/home/nick/Development/arduino-1.6.7/hardware/tools/avr/bin/avrdude -C/home/nick/Development/arduino-1.6.7/hardware/tools/avr/etc/avrdude.conf -v -patmega32u4 -cavr109 -P/dev/ttyACM1 -b57600 -D -Uflash:w:/tmp/build8f287ac41038dd4edf2d64ea95be7b6f.tmp/Blink.ino.hex:i
avrdude: Version 6.0.1, compiled on Apr 14 2015 at 19:04:16
Copyright (c) 2000-2005 Brian Dean, http://www.bdmicro.com/
Copyright (c) 2007-2009 Joerg Wunsch
System wide configuration file is "/home/nick/Development/arduino-1.6.7/hardware/tools/avr/etc/avrdude.conf"
User configuration file is "/home/nick/.avrduderc"
User configuration file does not exist or is not a regular file, skipping
Using Port : /dev/ttyACM1
Using Programmer : avr109
Overriding Baud Rate : 57600
AVR Part : ATmega32U4
Chip Erase delay : 9000 us
PAGEL : PD7
BS2 : PA0
RESET disposition : dedicated
RETRY pulse : SCK
serial program mode : yes
parallel program mode : yes
Timeout : 200
StabDelay : 100
CmdexeDelay : 25
SyncLoops : 32
ByteDelay : 0
PollIndex : 3
PollValue : 0x53
Memory Detail :
Block Poll Page Polled
Memory Type Mode Delay Size Indx Paged Size Size #Pages MinW MaxW ReadBack
----------- ---- ----- ----- ---- ------ ------ ---- ------ ----- ----- ---------
eeprom 65 20 4 0 no 1024 4 0 9000 9000 0x00 0x00
flash 65 6 128 0 yes 32768 128 256 4500 4500 0x00 0x00
lfuse 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
hfuse 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
efuse 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
lock 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
calibration 0 0 0 0 no 1 0 0 0 0 0x00 0x00
signature 0 0 0 0 no 3 0 0 0 0 0x00 0x00
Programmer Type : butterfly
Description : Atmel AppNote AVR109 Boot Loader
Connecting to programmer: .
Found programmer: Id = "CATERIN"; type = S
Software Version = 1.0; No Hardware Version given.
Programmer supports auto addr increment.
Programmer supports buffered memory access with buffersize=128 bytes.
Programmer supports the following devices:
Device code: 0x44
avrdude: devcode selected: 0x44
avrdude: AVR device initialized and ready to accept instructions
Reading | ################################################## | 100% 0.00s
avrdude: Device signature = 0x1e9587
avrdude: reading input file "/tmp/build8f287ac41038dd4edf2d64ea95be7b6f.tmp/Blink.ino.hex"
avrdude: writing flash (4456 bytes):
Writing | ################################################## | 100% 0.33s
avrdude: 4456 bytes of flash written
avrdude: verifying flash memory against /tmp/build8f287ac41038dd4edf2d64ea95be7b6f.tmp/Blink.ino.hex:
avrdude: load data flash data from input file /tmp/build8f287ac41038dd4edf2d64ea95be7b6f.tmp/Blink.ino.hex:
avrdude: input file /tmp/build8f287ac41038dd4edf2d64ea95be7b6f.tmp/Blink.ino.hex contains 4456 bytes
avrdude: reading on-chip flash data:
Reading | ################################################## | 100% 0.03s
avrdude: verifying ...
avrdude: 4456 bytes of flash verified
avrdude done. Thank you.
Can you please compare to what you get? Or post exactly what you see?