I'd had the same problem for weeks (ie. SSID not appearing on ANY computers) and came across a website that mentioned turning the Personal Hotspot on via Setting>General>Network, instead of the obivous Setting>Personal Hotspot.
It's now working!! So to reiterate, don't use the first Personal Hotspot option in settings, turn it on and off via General>Network> (scroll down) Personal Hotspot.
This is clearly a bug.
I found the recent iOS5.1 update didnt help, nor did switching flight mode on and off (with sometimes hepls with poor carrier data bandwidth).
The other option you could try (which I didn't need to) was to Reset Network Settings under General>Reset. (But I expect this may just reset the 3G data carrier settings and not all the phone network settings. If you try this I guess you may want to record you phone carrier settings first or at least have their tech support number handy in cse the iPhone doesn't magically find them from the network (or if you have an unlocked phone on another network).
All the best, hope it helps.