You didn't mention what OS you are using. So, if you are using 1.6 do this:
home page > settings . applications > scroll down to Market > press clear/reset data.
That should get you going. If you are on 2.1:
home screen > settings > wireless & networks > mobile networks > access point names
Do you have any "APN" postings in this window? If not, come back and advise. In the mean time, a work around would be to use your Wi-Fi, this, when activated, will allow you to get into the Market and the Internet.
Good Luck!