wow. 4300+ views and not even one suggestion.......?
Okay, here's a suggestion. Run diagnostics tools. Wireshark to see if the test is really happening, and SQL profiler to see if writing to the database is really happening. Or, you could call support and let them help you.
We had the same problem after re-installation of a core server. I opened a call and our TAM found out the solution:
In \Program Files\LANDesk\Shared Files\keys there is a protect.ini which reflects the core server certificate (the .0 file). They did not match after the re-installation. Just change the entry in protect.ini to the name of the .0 file.