Doh! It IS protected!

My apologies Dave. But from the Excel 2007 UI its not obvious - On the
Review tab/ribbon in the Changes section there's an icon staring at me
saying 'Protect Workbook'. I figured, logically, if the workbook was
protected it should say 'Unprotect Workbook'. It was only when I
double-checked in the Tools menu on a machine running Excel 2003 that
I realised it was actually protected.

Sorry for wasting your time.

- Nick