When you were running SP4, did the find computer icon ever work for you? If it did, what was done on the server before it stopped working?
I have never come across this function not working, and in my current project, where they have 6.9 SP2 and later, it works on all servers I have tried so far.
Have you tried installing DS onto a different server using the same install files to see if it works or not, because if it doesn't, then it could be your install files.
Another possible cause could be some security config on the server itself, so if it fails on a new server, test it on a completely vanilla OS built from its media and not from the corporate build process and do not join it to your domain. If it works in that environment, I would first join it to the domain to see if it still works or not. If it does, then there is a config setting within the corporate build process for the OS which is causing it.