Você está usando o Ubuntu One? Após a atualização para o Ubuntu 11.04, eu estava passando por circunstâncias semelhantes. Acontece que eu estava tendo um problema com a sincronização do Ubuntu One. Posteriormente, para mim, foi uma questão de fazer com que o Ubuntu One fosse sincronizado corretamente. Depois disso, Nautilus começou a tocar de novo. Se você suspeitar que isso pode ser o seu problema também, eu posso apontar para o post que detalha a correção para o Ubuntu One.