Knowing whether you have a PM or not depends entirely on whether you spot the difference in the top right corner. I've sometimes spent say an hour on this site and not realise I have a PM until a lot later, sometimes the next day.
How about:
1. A pop-up telling you you have a PM
2. Having the 'x are new' in white turn into yellow when you have a PM (more elegant IMO)
3. Have the 'x are new' flash?