First, someone needs to update the forums here to list 2.5.x series in the version dropdown, no?
Second, the link in WP 2.5.1 goes to:
Which has no compatibility list that I could find. So I just assumed (wrongly, natch) that all themes listed are 2.5.1 compatible. Nope.
It's a complete crap-shoot. You have no idea whether the theme you download is going to work "out of the box" or not. Out of the 3 I tried, only one didn't spit back an error on a clean WP 2.5.1 install.
The vast number of themes really are one of the core components of what makes WP cool. But with a theme site that doesn't seem like it was updated in the past 6 months, this really speaks to a disconnect between the developers pushing out code, and the folks responsible for ensuring all the supporting stuff (themes, plugins, etc.) work just as seamlessly as they always have.