Tente usar os caminhos completos
encontre seus caminhos:
$ which rhythmbox
/usr/bin/rhythmbox
$which rhythmbox-client
/usr/bin/rhythmbox-client
Em seguida, sub os resultados em vez de apenas os comandos
notify-send -i /usr/bin/rhythmbox "RhythmBox Is Playing" "$(/usr/bin/rhythmbox-client --print-playing)"