Okay, here's how it worked for me (T-Mobile G1 in UK).
Get your PUK code from your provider.
Get the screen where you are told the PUK needs to be entered and using the keyboard type:
**05*<PUK Code>*<enter a new pin>*<confirm the new pin>#
That will simultaneously unlock the phone and set up the PIN code.