Academy?
I just *have* to jump in with my 2-cents-worth...
Of course, nowhere have I read that they were all GRADUATING at the same time. Think about it - it's unlikely Kirk would have been given the E right out of academy, we know Spock was already on the E, etc...
No, more likely we'll have somthing like Spock coming to Earth to meet the new Keptin, while Kirk is prowling the Academy looking for people to fill out his crew. Scotty could be there eiher teaching or doing a touch-up course between assignments, ditto Uhura. As for Sulu and Chekov, they *could* have been graduating at the same time (or just about).
So, it *is* possible to write a consistent story behind their meeting... *if* you hire a decent set of writers who actually care about continuity.
BTW: I quite enjoyed ST:E - I thought it stood well based purely on the TV series and movies. I don't know about the books as I have read very few of them (and wouldn't consider them "canonical" in any way unless under special circumstances). ^_^ Oh, and I am *not* a Trekkie, nor a Trekker. I just enjoy watching the show every so often (although I tend to give ST:DS9 a wide birth. Gimme B5 any day over it. Whoops. No flame war please, my personal opinion. YMMV)