Did you recently upload a back-up of your database?
The new PM problem is based on PM. You may have downloaded a copy of the database while you got a new PM and it's saying you have 1 unread but the DB isn't showing a new PM. Just snoop around the DB for this.. I think it's in `users` table.
When it comes to Who's Online, not quite sure as I've never had a problem with it but it might be the traffic on your site or the DB not updating it properly. You may have uploaded a database while everything is going on still.
-Tip: When backing up a database, 'close' the site with the maintenance message and say something like: "Backing up, be back online in 10 minutes" or something like that. Then you won't ever run into any of these problems. BUT I may be wrong about the Who's Online one.
