Ok so this is what I finally ended up doing.
1. Took a *selective* backup of just contacts, calendar, Browser bookmarks and BBM contact list
2. Logged into Vodafone BIS site on my PC and deleted all the associated email accounts
3. Wiped the phone clean using BBSAK (BlackBerry Swiss Army Knife
4. Installed a clean (official) OS 126.96.36.1990
Package Version: 188.8.131.526
Software Platform: 184.108.40.206
5. After the firmware was loaded, restored contacts, calendar, Browser bookmarks and BBM ONE-BY-ONE
At this point, I figured that OS 5 (all versions) indeed have a bug in the calendar app. If the default view is set to "Agenda" (as it was in my case), the calendar takes a good 4-5 seconds to open up. However, once I change the view to "Date" or "Month", it opens up in a snap. Since the calendar was restored from the same backup file in all 3 above mentioned cases, I deduced that backup is not corrupt per se.
6. Logged into Vodafone BIS site on my PC again and set-up email accounts one by one