Hi,
I had a similar problem today and finally figured out that I needed network-cmds. In case you can't find it, make sure you have "Hacker" mode enabled under the Manage tab → Settings in Cydia.
I don't know if the order matters, but I did the install like this:
Install network-cmds
Install Tetherme
Reset Network Settings
Open Tetherme from Settings.app (note that the normal Personal Hotspot heading will not appear until after you enable the hotspot once from Tetherme, further down the list in Settings.app).
Lastly, in case anyone sees this, I think it was iCleaner's checking and removing of unused dependencies that messed this up for meTetherme and the "Personal Hotspot" setting were available in Settings.app, but upon enabling tethering, nothing worked (Wifi network never appeared, etc.).
Hope this helps!