I got my new Galaxy S one month back. I have no problems with any other functionality but Android Market. I can browse apps, but when I click install each get stuck at "Starting download..." screen, and never starts or fails. I had kept it for 3 days and still the same. Market / Google Apps / Download Manager clear cache / data does not help even. Phone restart also does not help.
So far the solution is do a factory reset and lose all current apps, then install 5 to 6 apps again. Then the same story begins. No more apps can be downloaded. Stuck @ "Starting download...".
"Samsung Apps" application works fine.
I also have tried all following firmware and problem persists.