Mobile hotspot not working?

[Chuck37]

I got the GS4 and changed to a share everything plan, but when I try to turn the hotspot on it says "Use of this service requires a subscription to mobile hotspot or mobile broadband connect". I was told specifically that it was included with share everything. Anyone have any ideas? I've tried customer support but gave up after waiting on hold for 15 minutes... I wonder if there is some sort of delay in going from my old unlimited plan? I've restarted the phone every once in a while to see if it will notice the plan change or something.