The other option is generally "chinatown" or anyone else who advertises that they unlock cell phones. Here in the bay area there are plenty that advertise on craiglist.

You could also buy yourself a cheap beater cell phone to use in the mean time. I don't know how attatched to your P800 your are, but I suspect having a small candybar phone like the T616 or even t68i might come in handy in other situations and would use all the same accessories.

Matthew