Como dicen por ahí, Ubuntu es recomendado a los usuarios que acaban de venir de Window$ y tienen conocimientos muy básicos de informática. Quizás sea por eso que da tantos problemas, además de que es de los linux más extendidos. También hay que tener en cuenta que es una distribución bastante joven con respecto a sus principales competidores (Como Opensuse o mandriva)
Eso pasa porque has movido los archivos de música del directorio en el que estaban cuando las agregaste a itunes. Lo que puedes hacer es borrar lo que tienes en itunes y ponerlo todo de golpe o bien añadirla una a una cuando te pone "encontrar" cuando intentas reproducir una canción.