Magento – undefined index in “toolbar.phtml” – after changing default sort by

Recently I added a new product-attribute and it was set to be the default sortby attribute. To my surprise, I used to get an undefined index on some categories.
I failed to get a clear solution in any of the article from Magentocommerce site. On further investigation I realised that just setting the default sort by option will not be sufficient.
It is also necessary to check if you have selected this new attribute in the list of “Available Product Listing Sort by” for the category which is causing this issue.
So I logged into Magento BE, and used following path
Catalog >> Manage Categories >> Selected the category that raised the error >> Display Settings [TAB] >> Available Product Listing Sort by
Her I noticed that the new product attribute was not selected!!! Seems Simple, still…!!!

I am not sure if this error can also get triggered when we use default Toolbar.phtml without any modification.

Additional info:

Related to: A custom designed toolbar.phtml which was primarily used to modify list of sortby options.
Scenario: Error gets displayed when I click on a root category or when I try to use magento search.
Quick Solution: Make sure you have selected this new attribute in the list of “Available Product Listing Sort by” for the category that caused this error.

I am sure this might be rare case, but it can happen. Happy shopping!