I just got this from the MS development team. If you are considering purchasing Excel 2013 and often use a macro to protect/unprotect many sheets at once I'd read the info below. In my case, in 2007 it takes about 2 seconds to lock 130 sheets in a Workbook Open event. In 2013, about 3 minutes. As for the suggestion in the last sentence, anyone have any suggestions on consolidating the number of pages and functionality relying on sheet protection?

From MS...we have verified with our product group that the behavior you’re experiencing is a result of the change in Office 2013 to use a more secure encryption algorithm that takes longer to run. As a result, it takes longer to encrypt the password for password protected sheets. For single sheet protection operations this isn’t noticeable, but when add-ins or macros unlock/lock sheets in bulk the result can be.

The product group has concluded that it’s something they don’t intend to fix in this version and unfortunately there are no workarounds other than to minimize the number of times you lock/unlock worksheets and only do it when they need to be modified. One suggestion is to consolidate the number of pages and functionality that relies on the sheet protected logic, so that fewer sheets and operations need to initiate sheet protection locks/unlocks.