I just had to get my account changed since it turned out the account that AT&T switched me to was not correct. I was getting partial Tethering but not everything I needed to in order to connect from everywhere.
My new data plan is the following: BlackBerry Enterprise Unlimited + Tethering
This is $59.99 before discounts and requires you to have a phone plan as well. I can now connect and all of my connecting will be unlimited.
AT&T via BES