I think the mistake was raising Kirk to the rank of captain. The writers didn't seem to understand that it's possible to be a captain without holding the rank of captain. He should have been a commander at the end of the film. Spock an Lt.C (like he was in the show) Scotty, Bones, and Sulu Lts. Uhura a JG, and Chekov an ensign.
They could have even gone a bit further and made Kirk an LtC and adjusted everyone else accordingly. While I don't think it's common for LtCs. to be captain now (At least in the US. I don't know about Brits/Canada/France/etc.), it wasn't that unheard of even as late at Vietnam. And seeing as how Starfleet just saw a massive loss in personnel, it wouldn't have been that big of a stretch at all to have a guy who was one of the top command graduates in the history of SFA and had just literally saved humanity to be promoted to Lieutenant Commander and given his own ship.
I would say the exact opposite, actually. The rank jump is weird and jarring, but ultimately a rank is just a title. Sisko commanded a whole station as a commander. Kira was given a starfleet rank of col. just so the Cardassians would take her seriously. Captains and even commodores have, at times, seemed to inhabit functions where they were basically glorified secretaries. Giving Kirk a technical promotion as a reward might have been stretching it a bit, but just that on its own would've been fine.
The thing that makes the whole story completely unbelievable is not the title, it's the responsibility. He isn't just given a promotion out of gratitude or respect - he's given complete responsibility over hundreds of crew and one of the newest, most advanced ships in existence. And he's given that despite barely demonstrating even the most basic aptitude for command - he doesn't come anywhere near the kind of incredible wunderkind performance that would be required to justify giving him such a huge increase in responsibility.
It doesn't make much sense.
But only a little less sense than Kirk getting a new ship at the end of TVH (semi-retired training officer who broke protocol and got his ship crippled by the Reliant; then stole the same starship (would that be piracy or mutiny?), breached a forbidden zone, destroyed his ship and commandeered a Klingon ship, thus inciting a diplomatic incident.).
Face it - both Kirks got a free ride.
(In the movies at least.)
Eh... That Kirk at least had a long and exemplary record, was proven right in his objections to SF about not rescuing Spock (which would mean zero in the real world, but Starfleet is idealistic that way), happened to simultaneously - and despite being severely disadvantaged - uncover and stop an already underway Klingon plot to attack Federation scientists, steal Genesis and use it as a weapon (which would've been a much larger diplomatic incident than what actually happened - probably a war), and save lives in the process, and then also saved the entire Earth for good measure (true, he wasn't alone, but he had much more of a hand in STIV's resolution than he did in ST09's, and the reward at the end of STIV was as much for the whole crew as it was for Kirk).
The only real problem I have with that from a plausibility standpoint is the fact that they did all start out semi-retired, running training missions and then sort of randomly transitioned back to active duty for no apparent reason. But that's a problem with the entire film series - with its constant waffling about whether or not its time for them to settle down and let the young people get on with it - not just the one decision to give them a new Enterprise.
Not to mention, there's a big difference between a plot hole that is never really explained by the movie, but which is at least conceivable (like Starfleet deciding that putting Kirk out to pasture was premature, or maybe just having a temporary shortage of experienced command crew) and a plot hole that just does not make any sense whatsoever (like taking a guy who's never even commanded a dinghy and putting him in charge of a warship).