There are two way of change the style of a Gantt bar.
The first, as you have already tried, is to change the Gantt bar style. This will change the style of all bars in each category.
The second way is to right click on a specific bar and choose Format Bar..., then assign it a different color. If someone has done this, then changing the style won't have any effect on bars that have style changes applied explicitly.
To manually change a bar style, right click on the bar that isn't conforming to the style rules, and select Format Bar...
The following dialogue box will appear - you can click the Reset button at the bottom of this dialogue and the bar style will revert back to its default.
If you have a lot of bars in this state (or if some are only changed subtly), it may be worth doing the whole project programmatically, which can be done by running the following code:
Sub ResetGanttBarStyles()
Dim t As Task
For Each t In ActiveProject.Tasks
If Not t Is Nothing Then
Application.GanttBarFormatEx t.Index, Reset:=True
End If
Next t
End Sub