Yo abrí un post sobre esto hará un mes o 2. Yo tengo conectada la consola al router por Ethernet, y el PC en el que tengo el media server lo tengo conectado por WiFi. El caso es que la opción de buscar servidores no me funciona, y sin embargo si no los busco, al rato de estar jugando o de estar viendo alguna peli, vuelvo al XMB y resulta que me lo encuentra la consola por sí solita, sin yo buscarlo.
Busca el post que te digo para más información, pero resumiendo, parece ser que el problema surge cuando el PC lo conectas por WiFi y la consola por Ethernet y viceversa. Parece ser que si los dos están conectados por Ethernet o están los dos por WiFi, el problema no pasa.