There is a limit of how much "direct" formatting you can apply in Project. You can apply formatting to Gantt bars by Bar Styles formatting - but the limitations are in the Text formatting. How many departments are you trying to track? Have you considering using a spare text field and filtering? Have you used the group field in the resource sheet to track departments? If so, you can add the Resource Group field to the table for highlight filtering.

Please also ensure you have Project 2010 up to service pack 2.