Doing this did the trick. The paths are replaced:
However, for some weird reasons, Clementine can now access the library in the right directory, but when it start playing a song, it just skip it. :S Something must have broke.
UPDATE subdirectories SET path = REPLACE( path ,'/media/sda3/Users/Admin/Music','/media/DATA/Musique');
I should try an alternative way, I know I can modify the playcount manually in the database without breaking it.
How could I export the whole "playcount" and "skipcount" column (to a text file?), then import it in a new blank database (That will be created by Clementine) ?
EDIT: I can select what I want with this: SELECT title,playcount,skipcount FROM songs but how can I export it, then import it in the blank database (Overwriting the content of the columns, which are 0 everywhere) ?