Corrigido meu próprio problema (+1 para o meu "usuário Linux" cred!):
O Unity tenta encontrar arquivos que você procura através do Dash, mas a configuração padrão para a ferramenta de indexação de arquivos que ele usa nos bastidores ("locate") lista um monte de diretórios e tipos de sistema de arquivos. O que você quer fazer é editar seu arquivo /etc/updatedb.conf e remover algumas dessas exclusões.
Para meu caso de uso específico, removi "/ media" da diretiva PRUNEPATHS e "nfs" / "cifs" da diretiva PRUNEFS . Se você, então, sudo updatedb para re-indexar o sistema, você deve achar que as pesquisas de arquivos do Dash se comportam como você esperaria.