Alright I have figured it out. The issue was mainly an oversight of when I was reading through the BluetoothGatt documentation. I was calling .disconnect(), but not .close(). Since the Galaxy s4 can only handle 6 connections at a time, my service was only running 6 times. Adding the .close() to my code allowed it to properly shut down the connection and freed up those used connections.
Source that made me re-read the docs more carefully!
So remember to use .close() on your BluetoothGatt object if you have a recurring connection to the same device(s)!!