How to visually indicate statuses in a matrix of information?

I'm designing a web app to help users track the status of several products over a 6 month period. We need to show a product's status for each month. A product has 1 of 5 statuses for each month.

I've designed this information to display in a matrix like this. I'm open to other approaches.

          July      August     September      October     November       December

Product 1

Product 2

Product 3

Product 4

Space is limited for each cell because we have to display other information. That's why we used colors in the previous design, but colors were problematic because of color blind issues. Here are my options as I see them:

1) Use a color palette that works well for all users. The tradeoff is the matrix will be very colorful and possibly distracting.

2) Use icons to represent statuses. Icons would still need labels, however, as statuses like "deployed" don't have intuitive icons.

3) Use labels. This would make the matrix noisier but the status of each cell would be clear.

Hopefully that makes sense. It's hard to describe this design problem with just text. Thanks for your help.