As long as the installer and uninstaller are well written then there shouldn't be a problem.
The reboot is required because the installer needs to replace a file that currently in use. This will happen when the system next reboots. You'd get the same when the application/service using the file was restarted.
The uninstaller should check to make sure that no other application requires a file before removing it from the system. I'm not 100% sure of the details but I think Windows (say) keeps a record of which applications use which dlls. When an uninstaller tries to delete the dll it decrements the use count and only really deleted if the count hits zero.
To be safe, if you are installing a new version of a program it's probably best to uninstall the old version before installing the new version.