Check out the battery cables. If you have any of those "replacement" cable clamps, get new ones. You've got a lousy connection there somewhere. Check battery voltage too, to make sure the car has not killed the new battery due to a short or something silly stuck on, like the trunk light or something. If the battery is below 12V, then put a charger on it, or hook up jumper cables and let the other car charge it for 20 minutes or so. Take that time to pull your fuel pump relay, and re-solder it or replace it. (Under right side of dash, up in front of glovebox). Also check your distributor cap for signs of corrosion- either replace it or scrape off the oxidation so clean copper shows on the pins.
Oh and when checking cables, don't neglect the negative cable. The cable ends need to be clean and tight, with no broken strands, and no white/blue/green/yellow corrosion gunk on them. After this little bit of work, if it still refuses to behave, I guess I'd think about replacing the starter. They're pretty tough starter motors though....
--
Rob Bareiss, New London CT ::: 86 244DL, 87 244DL, 88 744GLE, 91 244: 808K total