I have an answer for you, but you won't like it.
T-Mo US is phasing out the t-zones access and the epc APN. They are trying to get everybody on either their smartphone plans (way to expensive) or their unlimited web access (for non smartphones and the N900 if you are smart ) for $9.99 or something like that. This is for the internet2.voicestream APN.

I actually thought of that problem, but I doubt that can be it(could be wrong here). My reason is that I'ved tried using several other phones, ranging from smart to dumb, I don't get this issue. Another reason would be the fact that this happens too randomly spontaneous at areas that would work fine to be true. But once again, I could be wrong.

Is there any way that you can confirm it with what you just said?

"No cellular data available" will sometimes show when switching between EDGE and 3G with an active connection, or when you have a call (which, on 2G, turns off date transfer).

How old is your SIM? Have you considered asking for a replacement?

My sim is pretty old, probably a good three years already. Maybe it is a good idea to get a replacement. Just want to know, can I get the replacement for free?

But what I don't get is, how does all this cause me to unable to reconnect to my data connection unless I restart the device(not my cellular signal). And the fact that the problem will persist most of the time, therefore rebooting my device don't help when I get disconnected again after 2-6 minutes. What really annoys me more is that it's random and happens at places where I would have no problem with my data connection.

Why dont you try to get a new sim card? It sounds as if you had it for a while. Also try internet2.voicestream.com for the data connection. I use that and I am here in Chicago. epc.tmobile.com does not work as well for me here. I dont have the 5.99 plan but I assume the epx.tmobile.com is newer and since your plan is old maybe that is why it doesnt work. Just an assumption and I say to use that internet2 because I had similar issues early on. Hope I help.

It has nothing to do with phone. I had the same thing few weeks ago when my data plan exceeded 10Gb. All tho im on unlimited plan for smart phone Talk+Text+Web $60. T-Mo doing it deliberately if you got over that limit you still have connection but its very slow i mean.They keep it until next billing cycle. So thats probably the reason. Keep it on "Dual" so it will switch between 2G and 3G. (i use "3G/2GDual" app for that). At least you are going to have stable connection but still slow when its come to web. And about SIM card it need to be replace every year or two.