Are you sure its the firewall? I think that icon can be any security centre item, so firewall/virus/auto updates. I sometimes get a message saying my AV hasn't started up, but that's because AVG is still loading after boot up.
Not sure how you find out what the message is though.
You could isolate which security centre item it is by changing the way security centre alerts you, i.e. get it to alert you for one item at a time such as firewall, reboot, see if the message still appears. Repeat with virus and auto updates selected until it re-appears and then you should know.