I have to admit I have mixed feelings about Google's recent advice, because it's very complex (and they've oversimplified it), and it doesn't work well for all scenarios. If you're using this as prevention and don't have any major problems (like a Panda penalty), then I think rel=prev/next is a good bet here.
As Alan said, you should be able to remove the Meta Robots (NOINDEX), and that's probably sending a mixed signal to the crawlers.
For the sorts and other additional parameters, Google recommends you use rel-canonical to the root page. So, a URL like:
http://www.vistastores.com/patio-umbrellas?dir=asc&order=name&p=2
...would have the following tags on it...
In other words, canonicalize to page 2 (with no additional parameters) but then rel=prev/next should reflect the sorts and other parameters of the current URL.
This is the main problem I have with the approach - it's extremely complicated.
Meta Robots (NOINDEX) is very effective for keeping the search pages out of the index and avoiding duplication problems, and it's much easier to implement. The advantage of rel=prev/next is that your other pages (2, 3, etc.) could potentially rank if they're a better fit. For internal search, like product search, I find that's almost never a big issue. It's much more important for article pagination (Google doesn't make this distinction very well in any of their recent statements).
Also, as Alan said, it's approved to just canonical to a "View All" version, if you have one and it's linked/available for users. That can create a huge page, though, so you have to take usability and load times into account.
Sorry, it's very complex - I need to do a write-up on this, as I'm frustrated with Google on the subject. Honestly, I still tell some folks to use NOINDEX, because it's just simpler and it's very effective and preventing duplication problems. Rel=prev/next is more subtle, but it does seem to work, if you can implement it properly.