check for voltage drop at the starter when you are cranking it.
it doesn't sound like anything is wrong with the starter, I'd agree with Mike about jumping it with a larger cranking capacity battery as a test. The batteries on these are barely enough to get em spinning, and condition depends on what test the shop did.
i bet it has voltage, but wouldn't pass a load test.
plus if you are doing this all right now, it is probably super cold which isn't helping.
try riding it around for a bit, under motor is warm, then shutting it off and immediately try to start it up again using the starter.