As a VA, this idea wouldn't really affect me, but I was toying with the idea and liked it. Figured I'd throw it out there, see what others think.
Rather than simply spending skill points, going to Quinn who says "Congrats! You're promoted go get a free ship!" I was thinking it would be cool if there were missions that would give you a reason for the new ship. Essentially, Quinn would say "We need you to go somewhere and do some top secret and totally awesome thing." And you go do it. Your reward is the promotion. Some missions may have him say "Your current ship won't do, go get a better one" (which is essentially what it is now but gives you a reason why you're retiring your ship), while other missions may have you use your current ship and at the end it gets significantly damaged (think Enterprise from STII WOK) and has to be decommissioned. As a result, you get a new ship.
This could even lead to some really cool and clever ways of getting the ship, such as perhaps Section 31 contacts you and you have to do something of questionable legality for them and you get arrested. You then break out of jail, steal a ship (think STIII) and narrowly escape Starfleet patrols with the help of your Boffs. Upon completing the mission for Section 31, you are cleared of charges and you get to keep the ship (presumably they pull some strings, since it doesn't make sense for Starfleet to say "You're a wanted fugitive and you stole a ship, good work! Keep the ship as a reward....for....breaking out of jail, stealing a ship, and saving the universe even though we don't know you did that because its super secret").
Sorry for all crimes against the English language here (I am sure they're there and I'm pretty tired so I'm not seeing them).