As I suspected, the starter is fine. The problem was with how I wired it (and the less-than-stellar directions which I followed to a T). I ended up needing to move the starter positive connection to the powered "right" side of the remote solenoid, remove the jumper on the starter prescribed for use with a remote solenoid, and add a starter signal wire from the "left" side of the remote solenoid to the spade lug on the starter solenoid.
I also wrapped the new starter in a thermal shield to keep it fresher longer.
Here's a pic of how I wired the remote solenoid. The black wire with the blue lug is the starter signal wire. The copper ring-lug with the red shrink wrap is power to the starter:
