I've seen that issue if an instance of the SD client already crashed on the machine and left a process running. (Check that no "jview.exe" process is running on the machine.) Also, the client can take an exceptional amount of time when first launched if the default app server it is trying to contact has crashed abnormally. Is this error happening with a single client or multiple? If it's multiple, have you restarted the SD server service?
Ok, so with that out of the way, if it's just a single client having the issue, first off, did you install the Microsoft JVM from the SD installation CD? What happens if you type the command "jview" on a command line? You should see some usage instructions if it's available. The version of the JVM on the SD installation (listed at the top of the usage instructions) is 5.00.3810. Chances are you've installed this correctly, but I'd try to eliminate that as the source of issues.
If jview appears to work correctly, I'd check to make sure that both the user and global cache has been deleted, because these files are preserved, even when you unistall SD. Check %SD_CLIENTHOME%\data and C:\Documents and Settings\[username]\Application Data\Hewlett-Packard\OpenView\Service Desk. I would take both of the folders above and rename them to "data backup" and "Service Desk backup" respectively. Each folder will then be reinitialized when the client launches next. So, after the renaming is done, try opening Service Desk again and see if you have better luck.
In my opinion, it's one of those issues, but if you're still having trouble, post back, and maybe we can troubleshoot it further.