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.8). 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.