Ok I tried New Zealand Vodaphone prepaid sim on my Nexus and I was able to access the paid apps in Market and purchase them as well. Tried Singapore's Singtel prepaid but it didn't work. All this was done via my home WiFi in KL