I just went through this same grief on Thursday/Friday, upgrading an old Treo to the Pre. The problem is that the data service is not recognizing your phone for some reason or another, easily identified by the lack of an EV logo next to the signal strength bars on the top right corner of your screen.
The fix involved calling the Sprint tech support number listed in the activation section of your owner's manual, from a landline phone in an area with excellent Sprint cellular coverage. Read the "You need to be connected" message to the person who answers the phone, and they should transfer you to the next level of techs with no further questions. When you get that tech on the line, read them the same message, tell them that your phone is not showing "EV" next to the signal strength bars, and that you suspect that there's a provisioning problem of some sort due to the migration of your data services from another phone/plan.
Here's the trick. Open up your keyboard, hold down the orange button, and press ###. Like magic, the [hidden] dialpad will open, and you can make calls or enter ## codes. In this case, you'll need to do a ##786# to do a hard reset of the phone, which will require the tech to provide the MSL code (which you should write down for future reference just because).
The tech that I was on the phone with had me do two reboots like that, and neither fixed the problem. She then tried something on her own, by having me turn off my phone and provisioning a "bogus" phone on my account. Then, she put my Pre back in. After one last ##786# reset, my phone went and activated itself once again, and came back to the Palm profile screen. Unfortunately, there was still no EV for two minutes or so...and then it magically popped up and everything has worked fine since!
Now for the cause of the problem. It either has to do with something about migrating from an old data plan/phone to a new one, or as my corporate reseller claims that it's a problem caused by powering on the Pre before you call in to have your old phone cut off and new one activated. Note that this is the first phone that I've ever owned that doesn't have step one of the owner's manual say plug it in and let it charge fully, and I'm guessing the reason is because plugging in the charger makes the phone turn on before it's activated. Ask me how I know.
Anyway, good luck with tech support. The people that I spoke to were top-notch, and were extremely patient over the 1/2 hour that I was on the phone with them. If you don't want to deal with them on the phone and have access to your Sprint account over the web, you may want to try putting your old phone back on your plan, and then put the Pre back. (Make sure that your old phone is powered off before you do this!) Of course, I don't know if there's a hidden charge to do this swap online, and I didn't have this option since my phone is on a corporate plan where I don't have access to the Sprint web portal.....