Tim,
Well, a new battery is great, but it has to be fully charged to work the starter. What is your battery voltage at idle and at 3,000 RPM?
You probably cleaned the battery cables and terminals when you installed the new battery, but did you also remove and clean the cable going to the starter motor from the starter relay? Both ends?
If you have done all the above, then you may just need to replace the brushes in the starter motor. They are available from MikesXS, of course. Removing the starter motor is not difficult, but you have to drain the oil first and one of the bolts for the starter motor requires an offset wrench to get to it.
You should also replace the seals for the starter motor while you are at it. One of the seals seals the inside of the motor case and the other is used to keep the oil from leaking out of the hole where the motor mounts in the crankcase.
Also, sometimes oil will get into the motor and the brushes if that interior seal is leaking.
