Does this same problem happen from all clients' computers? This
happened to me on just one of my workstations that has Office 2007 on
it. Others could see the presence icons, but I couldn't. We use
Office Communicator 2007 here.
Anyway, the solution was to delete and re-create my mailbox
connection in Outlook 2007. After that, I am able to see all
presence information in Outlook AND SharePoint.
Also, I've noticed that if a particular user does not have IM enabled
on their AD account, then no presence information will ever show for
that user.