As regards Uhura, she's not necessarily a different person biologically - just a person who lived a different life and learned a different profession. Her age doesn't pop up in dialogue, and her looks tell us nothing because the looks of supposedly "unchanged" people older than Kirk have changed anyway (and sometimes, elsewhere in the franchise, change even in situations not involving split timelines, always without comment).
With Chekov, that's not a possibility, as his age differs from the Prime one. But Prime Pavel claimed he had a brother named Pyotr in "Day of the Dove". Since our heroes are notoriously unaware of the siblings of each other, that may well have been true, and the parents in the Kelvin timeline just swapped the names of their two kids. This would be the minimum-fuss solution that would fit Star Trek's notorious lack of butterfly effect.
(So, does the Narada look like a regular mining rig? It sure fits my idea of a machine intended to hug and digest asteroids...)
Timo Saloniemi