Anything data relate isn't working? "Not subscribed to data service"

I just got my iPhone today. We activated it a few hours ago. Text and voice is working just fine but the internet is not.

Anything (email, safari, youtube..) where I need to connect to the internet gives me the "Could not activate cellular data network-You are not subscribed to a cellular data service".

So I called AT&T and he said I was signed up for the right data plan and to try turning it off and then back on again, which I had already tried.

I didn't have a data plan on my old phone, so am I just being too impatient (That's what my dad's saying ) or is there something else I can do?