- Make sure there is enough space on your phone to download the app.
- Reboot your phone.
- Make sure your Internet connectivity is good and your phone is connected to the network.
- Try logging in to Google Talk and then attempt to download your apps.
- Clear the data and cache from the Market app.
- If you recently received a market client update, please try to uninstall the app by following the steps below.(This is what did it for me!)

* Android 1.6 users:

1) Go to 'Home' > 'Menu' > 'Settings' > 'Applications' > 'Manage applications'
2) Press 'Menu', then touch 'Filter' > 'All'
3) Scroll down and select the 'Market' app
4) Touch 'Uninstall updates'

* Android 2.2 users:

1) Go to 'Home' > 'Menu' > 'Settings' > 'Applications' > 'Manage applications'
2) Press 'All'
3) Scroll down and select the 'Market' app
4) Touch 'Uninstall updates'
The Market application will revert to the original version, and you should now be able download apps.