Two possibilities occur to me:
1) When you protected the sheet, there was a check in the 'Edit objects'
checkbox in the Protect Sheet dialog.
2) The picture itself is unlocked. In XL2007, right-click on the picture >>
Size and properties >> Properties tab >> make sure Locked is checked. In
XL2003, right-click on the picture >> Format picture >> Protection tab >>
make sure Locked is checked.