Problem solved!!
Instead of changing the actual background itself, using the reference of the background solves the problem.
private void HighlightButton(Button btnToHighlight)
{
SolidColorBrush sBrush = (SolidColorBrush)btnToHighlight.Background;
sBrush.Color =
btnToHighlight.Background = sBrush;
}
Implemented this for all the buttons. Voila!!!