A ver, te cuento la historia entera por partes porque no sé lo que sabes y lo que no.
Cuando salió el Uncharted, la PS3 aún no tenía lo de los trofeos. El Uncharted sí tenía lo de las medallas, pero era sólo dentro del propio juego.
Luego sacaron lo de los trofeos en la PS3 y a partir de ahí los de Naughty Dog sacaron una actualización que añadía soporte de trofeos al juego. Básicamente creo que hace una correspondencia entre las medallas "internas" y los trofeos "externos".
Eso sí, como pasa con todos (o casi todos, no sé cierto) los juegos, una vez aplicado el parche los trofeos no se dan con caracter retroactivo, así que te toca empezar un nuevo juego y ganar esas medallas para que te dé el trofeo.
Así que la pregunta es: ¿Has actualizado el juego? Si tienes la PS3 conectada a internet creo que lo hacía automáticamente al cargarlo, pero no lo recuerdo bien.