Several possible things wrong here... either crawling problems or SEO problems (which drop-down menus tend to produce).
I'm not a fan of drop down menus even if they are crawlable, though. Drop downs make it too easy to put almost global site maps on all your pages, thus presenting too many choices, both to Google and to users.
This is a usability problem that I believe Google also sees as a search problem. The large number of nav links in drop downs completely fuzzes any hierarchical navigation structure, and the excessive number of links makes a strategic distribution of link juice almost impossible.
If the "long columns of navigation links down the left side of [your] pages" were really very long, though, you might have had too many links anyway. Most sites I audit or review have way too many links from home. Drop down menus are one of the big contributors to this problem.
I should add that the number of nav links you can use on home varies according to the authority of the site... and the kind of linking that can be done on Amazon (or on many large sites), eg, can't be done on smaller sites with weaker inbound linking.
On the other hand, on a small enough site, you can probably get away with a global nav structure reasonably well, so many sites that use drop down menus don't appear to have any problems.
On the usability issues of drop downs, see this classic thread by tedster from back in 2004... Mouseover Menus - or DHTML indigestion http://www.webmasterworld.com/forum21/7279.htm