Simple solution that helped for me on several phones.
- Exit all applications.
- Go to Settings => Accounts & Sync => Uncheck Background Data and confirm
- Quit all screens with back button
- Start Market => You will receive a message that Market can't run without Background Data => click Activate => Enable Background Data and click the back button
- Now test Market again