This issue is pretty interesting, and the OP has provided a LOT more detail than you usually see when somebody posts about some sort of issues. My first comment is that coincidences are not that common especially in the automotive repair game. What that means is that the OP states they never had an issue prior to replacing the battery, and immediately after replacing the battery the issue started. The chances that something completely unrelated to the battery replacement (or some sort of sensor getting accidentally hit or wiring pinched in the process of replacing the battery...) suddenly failed at this time would be quite the coincidence and therefore very unusual. The first step I always recommend in this situation is to look closely at the repair you just did....again, not just the fact you replaced the battery but is there anything around the battery you might have accidently hit or damaged? Did something short out when you rehooked the battery cables?