If you look at Review tab > Changes group > Protect sheet, you'll find the dialog box has a lot of tick options, including one to allow the user to format cells. Tick that one, and they should be able to change the colour even if the cell is protected.
Bookmarks