When trying to connect to my browser, I get the error message: "Unable to connect to the selected Mobile Data Service, please try again later. If the problem persists please contact your administrator."

I reset the TCP to the following, removed the battery and restarted the computer with no luck:
APN:WAP.CINGULAR
Username:
Password: CINGULAR1

I'm wondering if having AT&T as the new provider makes a difference. Any ideas for how to get the browser working?

This is a BES issue. MDS is a BES component.
You should seek assistance from your IT department.

I ran into a similar issue. I am an admin on my BES, and it is in fact a BES issue with the MDS server. My issue (possibly yours) is that a recent java update moved the /bin folder containing the .dll needed to start the MDS service to a newly created folder containing the newest version of java.

The fix was quite simple and I found it by doing a google search for the error I got when I tried to restart the MDS service. I haven't posted 10 times yet, or I would post the link, but do a google search for the following and it should be the first link:

"Error 203: The system could not find the environment option that was entered"

Basically, it just required a quick regedit to the key mentioned in that knowledgebase solution - change the path of the java folder to the most recently installed version (in my case jre6). After that, it was a simple matter of restarting the MDS service and my users were able to browse again.

Don't forget to backup your registry before making any changes.

Hope this helps.

-Jason