It did that on my 2G. Did you come from a 2G? They they you don't have a data plan. You just need to call them and add it back. It wouldn't let me add it online.
I get that error all the time when i check email on my 3G
I was at the apple store one day and i got it...I asked the genius and he told me if i continue to get it to go to AT&T and they will have to replace my sim card.
So if you are going from the original iphone 2g to the new 3gs and ordered online through apple the data plan will automatically update with no need to call at&t?