I am on 3 with a blackberry data plan.
I have an error message whenever accessing the app world which is 'you are not connected to the wireless network.'
When trying to connect to the browser I am told that 'there is insufficient network coverage to process your request.' Despite being able to send and receive texts and calls, and having full 3g coverage!
I am not using wifi to connect unlike all the other threads I found with this issue.
Any ideas??

Does email, bbm and other email related services work correctly? If not then you don't really have a BB data plan or it isn't provisioned properly.

Try resending your service books (see the FAQ if you don't know how) and do a battery pull - with the device on, remove the battery for 30-60 seconds, then put it back in and let it reboot.

Might want to try this a couple times. If it doesn't work, then you need to call your carrier.