I run into the same problem yesterday when I upgraded automatically (i.e. via the joomla control panel) to joomla 2.5.8 (from joomla 2.5.7) and cb 1.9 (from 1.
. after the upgrades there was no link to cb in the backend admin menu.
what helped, though, was a manual (re-) installation of cb. after that installation the link to cb in the backend admin menu was there again. it just took a few seconds to solve it. so may be worth a try.