So having lost my SIM (long story) for my Google Nexus S and having a new one posted to me the very first thing I did was lock out the PIN by putting it in three time wrong. Bugger. After ‘Hitting the Googles’ ™ here is the full solution to this problem:
1) Get your PUK Code by contacting your mobile provider (from another phone) so O2/AT&T etc and ask for the "PUK code". After a security check or automated system in my case, they will give you an 8-digit number this is very important, write it down and keep it safe. Double check it is correct this is your PUK Code/number.
2) On the Nexus phone (with the SIM in!) tap "Emergency calls only" button and you will be shown the usual dialer it won't call any emergency services (unless you type in 999/911 etc!), just shows you the dialer.
3) Think of a new 4-digit PIN number.
4) Type this magic code into the Nexus's dialer:
**05*<PUK number>*<New PIN number>*<New PIN number>#
If you have the PUK code 12345678 from your mobile provider and you want your PIN to be 1234 type:
Do not get this wrong more than 10 times, it will lock out you SIM for good and you will need a new one, this is a bad thing.
Thanks to ‘Nicklansley’ from http://www.nexusoneforum.net
PUK = PIN Unlock Key