I just bought an HTC Desire S and cannot download apps from the Android Marketplace. I tried to download Skype and it stalled saying "Starting To Download" - nothing happened. Then I tried downloading another app and then it said that app will be soon downloaded, but nothing happened.
Try clearing the cache and data of the Market application.
I think i found the problem. I turned option off that lets use 3rd party apps internet connection as was recommended on one blog on power plan optimization on Android.