A mi me pasaba lo mismo, según qué videos no me aparecian en la PS3 (y eso que los tenía en la carpeta "Mis Videos")
Lo que hice fue en las opciones del WMP11 darle a una opción que es Actualizar Biblioteca o algo parecido y ya me aparecían todas desde el menú de PS3. Logicamente, sólo verás las que acepte PS3, pero para ver video mediante streaming, funciona correctamente...