I have a worksheet where the cells are locked and password protected. When a
user tries to click in a cell, they get Excel's message the the sheet or cell
is protected go to the Tools menu... Is there a way I can replace this with
my own custom message? I have a button on the toolbar for the user to click
to lock and unlock the sheet so rather than tell them to go to the Tools
menu, I just want to tell them to click the button. Thanks.

Try this. I think It's what you want, well I hope so anyway!

Private Sub Worksheet_SelectionChange(ByVal Target As Range)
If Target.Locked = True Then
MsgBox "My Message", vbInformation, "My Message"
End If
End Sub