I had this issue with my 4S on ios 6. I emailed the Devs and they had me try a few things (the usual stuff, reset, re spring, reboot, set back to default) none of which worked. The last thing they told me was to uninstall all my tweaks and test out why there was no connection. That seems a bit extreme. I didn't have a bunch of random tweaks installed. I only jailbreak for about 10 things (gridlock, springtomize, etc.)

So I never went through with it. The wifi hotspot works, do I just use that.

Move to the present. I now have a 5s and am jailbroken on ios 7.0.4 and I'm STILL having the same problem. I'm trying to get on demand to work with my iPad mini. Each time it says "Failed negotiating" immediately after I try to authorize my iPad. This is just insane. Anyone with answers I'd appreciate the help. Uninstalling all my tweaks just to "test" a conflict doesn't seem right to me.