Tethering / Portable Wifi Hotspot Samsung Captivate
Here is what worked for me:

I connected my laptop using USB tethering, which worked immediately on the first try. Once I had done that I disconnected from USB and tried enabling the portable hotspot again. This time, connected devices could use the internet via the hotspot.