We had a site that was creating 1000's of pages with duplicate content so we installed the rel-canonical plugin months ago. (SEO Rocks).
We also activated the ajax pagination to avoid google from crawling the page 1 / 2 / 3 /4 .
My issue now is that many products are in the index , probably from static sitemap but are not getting ranked.
This is after we discovered that all brand pages had robots no-index on them (removed last week).
I have now (today) taken off the Ajax pagination on brand pages and I hope it will cure the problem.
Your issues could be a multitude of things, without seeing the site and source and running some analysis on the pages, it'd require an SEO book to be posted in this thread to give you an idea of what might be wrong.