After multiple phone calls and emails to Network Solutions we found out that it's not possible to redirect HTTP to HTTPS with their shared web hosting packages due to their SSL proxies. I upgraded to their Virtual Private Server solutions and it works great now.