I have Better Store Search installed and sorting does not work.

Please open file app/code/community/TBT/Bss/etc/config.xml

and remove the lines:

<catalog>
<rewrite>          <product_list_toolbar>TBT_Bss_Block_Catalog_Product_List_Toolbar</product_list_toolbar>
</rewrite>
</catalog>