1) Not much content on that page exclusive of navigation.
2) Not enough site trust.
3) Not enough links pointing directly to that page, the category (state) pages, or leaf node pages, like the individual hotel ones.
Prior to Panda, a domain with a lot of links could have virtually infinite leaf node pages with no links but laser-targeted content and rank a large portion of them. These days, "lots of links to our homepage" plus virtually infinite pages with no links is a recipe for being Panda'd.
I don't think the core "top -> state -> hotel" structure is likely a problem. That sort of tree structure, with variations, is pretty much universal in large sites. Having a lot of links on a page will not, by itself, burn you to bits.
You're absolutely right that there is not much content on that page exclusive of navigation, but in its defense the whole point of the page is navigation :) And it is just one page out of hundreds of thousands of pages on the site, many of which do have a lot of content.
I like your point about leaf nodes. Many of the domains that rank now either have a small # of pages total, or are extremely large brands with a lot of "trust", however Google defines it. In fact, these factors seem to outweigh having any original or useful content on the page itself in many cases (see post below).
If the problem is about too many leaf nodes, then cutting down "thin" content nodes (pages with little content, photo pages, etc) should have a positive effect. We've done a lot of this, so it will be interesting to see if that is the case.
As a concrete example following the Hawaii theme, we used to rank pretty well when someone searched for "Hale Koa Hotel" (a hotel in Hawaii).
Here is our page on it:
http://www.travbuddy.com/Hale-Koa-Hotel-v189806
It's got a few detailed reviews and candid photos from active members of the site. Certainly not perfect, but I think it's helpful and that it provides a different perspective. Right now it's ranked #55 on my browser, and here is a sampling of the sites that rank above it:
#9 http://old.armymwr.com/portal/travel/recreationcenters/hale_... (a site that just links to info from the official page)
#11 http://www.frommers.com/destinations/oahu/H42763.html (A trusted brand but limited original information about the hotel and no photos)
#14 http://www.dollar.com/Locations/gen.aspx?locationId=HNLC02 (no content at all)
#15 http://www.gohawaii.com/listing/Dining/90173401_HaleKoaHotel... (no original information)
#17 http://www.wedhawaii.com/hawaii-wedding-locations/oahu/halek... (a wedding photo album site, but no specific information about the hotel)
#20 http://hotelandtravelindex.travelweekly.com/Destinations/Hon... (no original information)
#21 http://gohawaii.about.com/library/gallery/blwaikiki_hotels_4... (1 photo, nothing else)
#25 http://travel.aol.com/travel-guide/united-states/hawaii/hono... (hardly any information)
#28 http://www.maplandia.com/united-states/car-rental/honolulu-h...
...
I'm not arguing we should be #1, or even #10, but we're certainly better than many of the sites between #1 and #55, and we've seen this pattern repeat itself for most of the hotels and pages we have original and unique content for. While we certainly don't have as many hotel reviews as TripAdvisor, we do have more quality reviews than most other sites, and we have to start somewhere :)
I guess a better question would be, if we have 75,000 reviews, what is the best way of internally linking to them within our site WITHOUT looking like a link farm? We're just trying to put our best content forward, so any suggestions would be appreciated!
We've been focused on hotels in this specific example, but the same argument could be applied to any travel destination. If you're planning a trip somewhere, would you only want to get information from the official tourist bureau and the hotels themselves, or would it also be beneficial to see candid reviews, blogs, and photos, and interact directly with other travelers who have been to the same place? I would argue that the value provided by that information is worth a lot more than 2%.
The average traveler researches 2-5 sites before booking. and a large % of them are motivated by a desire to read reviews (http://www.phocuswright.com/library/fyi/427). Clearly there is some value provided there, and if we can provide relevant and unique information that leads to a sale, or profit off the sharing of such information through unobtrusive advertisements, then I don't see any problem with that.
And if we can provide more useful information than our competition (many of those sites listed above have almost no original information at all), then I also see no problem with ranking higher in the search results.
That's not to say we are 100% there yet for every destination, but I believe we do have a ton of valuable information, and our goal is to get to 100%.
Also, get backlinks into your site for keywords like hotel reviews. To do this you can tell your reviewers to post on their blog twitter or Facebook that they just wrote a smashing review, and then place a link to their review.
Look at this page: [http://www.travbuddy.com/hotels]. All those links to "Hawaii Hotels" and "New York Hotels" look exactly like an old-school linkfarm.
Ask yourself this: if you're Google, and somebody is typing in "Hawaii Hotels" to do a search, is your Hawaii Hotels page really something they want as a top result? I don't think it is. Your content is not really "canonical" for Hawaii Hotels, it's just a page that lists a few reviews you've managed to collect.
It's all speculation on my part, since I have no inside information, but essentially, I think you're sort of poisoning your own reputation at Google with all those links.