yep, you surely hit a hint there.
The strange REBOOT needed in some case when you have broken dependencies …
Normaly, you never-ever reboot a server. Found out when playing with php/apache2 switch/upgrade, sometime a service restart or stop/start is not enought.