Hola
Yo uso Debian y me ocurre lo mismo desde que he cargado arduino 1.0 y en mayor medida con las placas uno, por lo que yo he observado me ocurre sobre todo con programas que envían muchos datos por serie desde arduino, que creo que mientras hay comunicación linux mantiene el puerto bloqueado.
La forma que he encontrado para poder reprogramar los arduinos es pulsar el reset del arduino mientras lo compila y soltar cuando empieza a enviar el sketch, no siempre me funciona a la primera pero en un par de intentos suele funcionar.