Thanks all for the tips. i ended up going to with Starhub. I went to the 3rd party store at Sun Plaza. The signup was a breeze. They were very accustomed to dealing with foreigners.
After using the phone & service for a few days, I can say I'm pleasantly surprised. The 3G speeds are on par with what I'm used to in Japan and USA. The coverage is a little spotty on the north side of the island, but I'll mostly be using it downtown and that seemed fine. Thanks again forum.
