Enter PIN to lock SIM. 1 attempt remaining.

Well, it sounds like the quickest way to set a SIM PIN is to lock yourself out.
After spending about an hour on hold (over 4 phone calls), no one seems to know what the default SIM PIN should be.
The last Apple specialist said the only thing they could find said the default was 0000. Even though I thought I had tried that one, I figured I must have typed something else the first time and tried the 0000 code for my 3rd and final attempt.

Oops. Now I joined the iBrick club.
For anyone who wants to know:
1) If your SIM card gets locked out you can still get to the ipod functionality of the iPhone but not much else.
2) Emergency Dialing with a locked out SIM does NOT allow all numbers to be dialed (as it does with a non-locked-out SIM), only REAL emergency numbers (although I didn't actually try dialing 911, I assume it would work).

The incredible part about this whole thing is that once you lock-out your SIM by trying 3 wrong PIN combinations, it takes AT&T about 30 seconds to look up your PUK code and you have converted your iBrick back into an iPhone.

Also, now that the AT&T wireless web site is working again, you can retrieve your PUK online from a link on your account summary page.