James, One thing you should have done when you had the shift motor removed is that you should have replaced the very thick, gummy, Honda grease with some new White Lithium grease. The old Honda grease makes it very difficult for the gears in the shift motor to move freely.
Note: Not all new batteries are good batteries, and the condition of a battery can not be determined by just measuring the battery voltage. It can have voltage without being able to deliver current (AMPS). Do not put a battery charger on your new battery for very long or it can damage your battery. Instead, charge your battery (slowly and carefully) with a battery maintainer such as a Battery Tender.
Last, are you trying to shift through gears while moving or when you are stopped. (The White Lithium grease will allow your shift motor and gears to work much more easily!).
USFS Motorized Trail Maintenance Volunteer