Go to menu > settings > applications > market > clear cache.

Then restart your phone.

Clearing the cache usually does the job for any problems I have with the market.

Also, be sure you're connected to the net - I take it you can browse the web?

 

I assume you're also on the new Market - if you want a solution that doesn't require restarting simply delete all the Market data, rather than just clearing the cache. When you go back into the Market you'll get the prompt about accepting the terms and conditions again, but after that things will be good (for a while at least, I'm doing this once a day at present).