I hate digging up old threads, but I figured I will let people know what a "true" answer is (at least in my mind).
Problem -- Users cannot add many web-parts to subsites even though they have "Full" control on the site. They are however restricted from the top level site. They live in their sub-world and have no reason to come out, and the company prefers it that way :)
Work-around -- Give users read access to top level site. This unfortunately doesn't work when you have sensitive data higher up than you want the users to go (I know, flaw in site structure design, but that is besides the point). We cannot give users access to higher level sites..
Real problem -- Users only on subsites do not have access to any of the top-level site galleries (web part, masterpage, content type etc...) And galleries only exist at the top level site
Real solution. Add them to the gallery permission level (Site actions - Site Settings - Web Part Gallery - Settings Gallery Settings - Permission' - Break inheritence, add what you need)
Am I missing or forgetting anything? Hope it helps