Eu também notei isso em lançamentos recentes do Ubuntu (15.04 notavelmente). Você já deu uma olhada no Launchpad, por exemplo:
- Bug # 767423 “O NetworkManager não mostra o ponto de acesso disponível ...”: Bugs: network- pacote de gestor: Ubuntu .
- Bug # 1332904 “O gerenciador de rede parou de procurar por redes wifi ...”: Bugs : pacote network-manager: Ubuntu
Normalmente faço sudo iwlist scan
como solução alternativa.