I'm not crazy about the idea of Sulu being Spock's first officer during the Enterprise's training years. As you said before, it'd be nice to think that these characters had careers between movies that weren't limited to just one starship.
Plus Kirk mentioned it was nice to have Sulu back at the helm for three weeks in TWOK which implies he was somewhere else prior to the training mission and was going back to that place after the training cruise ended.