Hi there,
This is my first reply to this board, so I hope I don't state the obvious or something you've already tried. This board is great, so loaded with great info. I've owned 6 Subbies so far. Currently, a '91 Loyale w/5spd and '92 Loyale w/AT.
Your problem sounds like battery terminals to me. Take them off and clean them, then reinstall and use a sealer or just some lithium grease. I bet that cures your grief.
This happens a lot, especially in humid areas or at times (like spring) when there is heavy dew. Your old battery terminals and the clamps had good tight connection and were somewhat sealed. But, if you take a close look anytime you disconnect a battery, you'll find a small amount of corrosion because you can't make the connections air/water tight. So, a small amount of moisture gets anywhere there is an airgap and over time causes corrosion where the tiny gap allows. The pattern on the clamp matches the terminal and gives you sufficient contact. Now, you've taken a new battery that doesn't match that pattern. Even when you clean them both, you still have two rough surfaces trying to mate together. So, after a week or two, sometimes less, you have corrosion in the connection. All the low amperage accessories will still get plenty of juice for there needs, but the heavy draw of the starter is to much for the small surface areas that are left in contact. So, you get the "clik, clik, clik" of the solenoid because it can't get enough juice to fully engage or you get nothing at all. That's my .02.
Have a great weekend, Stretch