I seem to be having the same problem as repent in the original post. I've uninstalled UM and MSDE several times and still cant get a connection going.
After uninstalling the first time I get errors when reinstalling when the MSDE is trying to configure so I assume something is being left behind in the registry.
Any ideas on how to get rid of everything completely, besides restoring the workstation to a previous state.