I still visit the repository when viewing plugins... can't seem to view/sort by the same degree when browsing only via the 'add new' interface on the wp-admin (maybe I am doing something wrong?)

Like others, I also go by 'latest update' and 'frequency of update' to determine whether or not a plugin is suitable for my purpose. I know that Tobias (of TablePress fame) does encourage people to give a rating/review in his correspondence, like Justin Tadlock said, and it seems to work quite well.

Some niche plugins have not been updated in awhile yet they still work. I like the idea of 'major update' compatibility (as suggested by Chip) - it would certainly be nice to have a 'It works!' button after installing (or It doesn't work! with a quick popup for users to explain why) for convenience.