s/\.\.\\.\.\/\/media\/usr\/part\/dir\//g
Este comando sed está errado, porque tem um \ faltando antes do primeiro / , o que leva o \ anterior a escapar como um literal / (alterando o padrão e "comendo" o separador) e, para o propósito de substituir uma única ocorrência de ..\..\ em cada linha, ela tem uma% excessiva de g no final; em qualquer caso, falta a substituição dos caracteres \ pela parte de caracteres / .
Use este em vez disso; Tomei a liberdade de mudar o separador para me livrar de uma provável síndrome do palito inclinado e alterar ; com + para melhorar o desempenho do comando em um grande número de arquivos:
find /home/user/directory -name \*.m3u -exec sed -i 's|\.\.\\.\.\|/media/usr/part/dir/|; s|\|/|g' {} \+
Saída:
~/tmp$ cat playlist1.m3u
..\..\path1
stuff
..\..\path2\path2
stuff
..\..\path3\path3\path3
stuff
~/tmp$ find . -name \*.m3u -exec sed -i 's|\.\.\\.\.\|/media/usr/part/dir/|; s|\|/|g' {} \+
~/tmp$ cat playlist1.m3u
/media/usr/part/dir/path1
stuff
/media/usr/part/dir/path2/path2
stuff
/media/usr/part/dir/path3/path3/path3
stuff