This is a problem that suddenly appeared (or rather didn't!) on my Nexus One running Cyanogenmod 7.
It was fine and then all of a sudden I could no longer load any emails in any of the labels, it just says "loading conversations" but never loads or times out. Search is affected the same way.
I don't often have to use labels so I put up with it. However, it is still happening on my new Samsung Galaxy S2.
Choosing to sync specific labels for offline access means I can get to them fine, but it's impractical for all labels.
As suggested by Google mobile help I tried deleting the data for the Gmail app (though there is no additional "gmail mail storage" app) and rebooting before re-syncing, to no avail.
During all this I have always been able to access labels on my 2.2 tablet and having just reinstalled CM7 on my Nexus One am now able to access them fine.