Try shutting your phone off for about 30 seconds.
Start it back up.
If you dont see any signs of a connection being made in the upper left corner, then check your sim bay.
One of the contacts could be slipping on the chips surface...
Dont know why that would happen so soon though, as the phone is BRAND new.