Check your filter settings in the market. For some reason they have a content rating on apps. Anything above the level you are set at won't download. Its really silly IMO because each user can change the settings meaning a child can change the filter to "all apps" and still download everything.