Sounds like you uninstalled UddeIM without uninstalling its CB plugin. We can't do anything about that as that's UddeIMs CB plugin and not ours. Private Message System does integrate with UddeIM, but only does so if UddeIM exists otherwise it completely ignores all UddeIM functionality.
To uninstall UddeIM completely I assume you need to uninstall its components first. So any CB plugins, Joomla plugins, or Joomla modules related to UddeIM must first be uninstalled then finally uninstalling UddeIM component. As far as I'm aware this has always been the uninstall process for UddeIM, but you may want to let the developer know below as the CB plugins should be non-blocking and simply do nothing if the component doesn't exist.
www.joomlapolis.com/forum/25-uddeim-plugin-and-component
Please note we only host the UddeIM support forums. We are not its developers. If you have any further UddeIM issues please post them to the above forums.