Awesome - unlock worked perfectly.

However, when I reconnected the phone to iTunes, it offered to restore my settings from a backup.

Not a full restore, just to reload contacts etc.

As soon as I did this, it gave me a "wrong sim inserted" message, and wouldn't work with my non-at&t sim anymore.

FIX: I did a FULL restore in itunes (1.0.2) and then set the phone up again from scratch. It's connected to my sim's network again, and everything is looking normal.

So in conclusion: Don't panic if you lose your network after reloading your settings in itunes, it's just that in that backup, the phone settings probably have it locked to at&t. Restore and all will be well.