Despues de hacer varias pruebas he visto que el problema no está en los formatos de video sino que en el DLNA (protocolo que utilizan los media server).
Los archivos de video los tengo en un disco duro en red y los veo en la PS3 utilizando el protocolo DLNA. Tengo un disco duro LACIE.
Probe con el TVersity y PS3mediaserver y todo va perfecto, sin embargo con el LACIE sigo obteniendo el mismo error para casi todos los archivos.
Sospecho que con el nuevo firm han hecho alguna pequeña modificación en la implementación del protocolo ya que el disco duro no lo he tocado.