I am a blackberry admin and I have had the same problem numerous times with new bberrys. My best guestimate is that it may be due to your wireless carrier. I have had the problem on both T-Mobile and Verizon. Call your wireless carrier and be sure that they have the data plan option turned on and that they are not denying your bberry their service books. If it does not fix itself that would be the first thing I would check.
If it works let us know, as other may have the same problem.