I have tried power cycling. Pulling battery still just sits at "starting download"
If you are trying to downloading a app and all you see is it sitting there downloading. I've had that happen several times. Just my guess is either the server is slow or down. You can close Market and it will download later when it can, or cancel the download and try again at another time.
If it's Market itself that's not working, I have no idea.