自分の場合は同機種でRhythmboxを問題なく使えるので、Rhythmbox自体はNetWalkerに対応しています。

Totemでは正しく再生できますか。
Rhythmbox導入後、プラグインを追加していませんか。プラグインによっては互換性の問題で、再生に支障が出る場合があります。

また、Synapticなどで再インストール指定した場合、設定が初期化されるわけではないので、完全削除後に再度インストールしてみてください。