This is a problem of Android Market.
Please try the following: From your home screen, press menu > settings > applications > Manage applications > Market > Clear cache.
Then start the download again.