Cyberhound and Bcaldwell85:
I'm one of the developers of MapQuest 4 Mobile. JSanders' recommendation about pulling the battery for a moment is often the best way to resurrect the network connection on a BlackBerry with connectivity trouble. It sounds from your comments that that hasn't done the trick in this case (i.e. I presume you have tried other downloaded apps that use the network and not had this trouble). Next step is to visit Settings -> Options -> Advanced Options -> Applications, select MapQuestMobile_BB8830 (or the like) and select Edit Permissions. Expand the Connections permissions. The setting for Carrier Internet should be set for either "Prompt" or "Allow." If not, I recommend "Allow."
Now, I have seen situations where a permission in this dialog said "Prompt" but the device behaved exactly as if it was set for "Deny". In that case I had to toggle the permission to "Deny," allow the reboot that the device asks for, go back into application permissions and set it back to "Prompt" or "Allow" to shake the problem loose. Admittedly, I've not seen a BlackBerry "lie" this way about network permissions (only with GPS permissions) but even within the same model and carrier different BlackBerries often have slightly different firmware, so it might be worth a try if you continue to see this problem.
If you've done all that (or as much as you're willing to try!) and still aren't having any joy, can you tell me whether the Network Error screen comes up more or less immediately when you launch the application, or does it display only after about 30 seconds? When you first downloaded and launched the application, were you prompted with a system dialog to allow the application to access the network, or did the screen go to the Network Failure message without such a prompt?
Thanks for giving our app a try and helping us determine if there's anything we need to do to address the problem you experienced.