When I had the issue on my workstation with the missing presence icons,
the problem was really with my client workstation / software, and not
sharepoint itself. (I do have Office 2007)
The solution ended up being as simple as deleting and re-creating my
Outlook profile.