In case it may help others, I'll try to list all my steps here. Please note, this is for a 3G phone which I later found was on 05.15.04 modem firmware (baseband), which can't be unlocked. I needed to upgrade to the IPAD Baseband 06.15.00. I also used a PC rather than Mac.
Here is the process which worked for me.
1. Follow this link exactly to jailbreak the phone first.
iClarified jailbreak using redsn0w.
notes:
When you download the ipsw in step 1, use "save" rather than "open" and when it finishes saving, right click on the zip file, left click on "rename" and then change the .zip extension to .ipsw instead, then hit enter, then "yes" to the box asking if you are sure you want to change it. Don't attempt to unzip the file. When you change the extension, the file works exactly as the instructions suggest.
To get iTunes to go to restore page, I had to place the phone into DFU mode (iTunes sees it as recover mode) BEFORE step 2 of the instructions. To do this, hold the power button (top left button) down for 3 secs, then without releasing the power button, press and hold the home button (centre bottom) down for a further 5 secs and then release the power button whilst still holding the home button down for a further 15 secs. The screen will go blank and when you plug it into iTunes (step 2 of the instructions), the required screen will display asking you to restore. It is important to then press "shift" restore (at the same time) not just restore.
At step 8 of the instructions, check the box "Install Ipad Baseband". I didn't realise that my firmware was one of the two that couldn't be unlocked, so I needed to upgrade the firmware as well. A warning appears, but as I couldn't use the phone anyway, I chose to accept the risk.
After the "shift restore" process (carried out before step 2), I found the phone could be turned off OK for step 9 of the instructions.
2. After completing this first step ENSURING ALL STEPS WERE TAKEN, then follow this link for instructions to unlock the telco.
iClarified telco unlock
notes:
Ensure you enable WiFi so Cydia can update first before the steps in these instructions, which includes a reboot.
The final step of mine said Reboot, not restart springboard but the rest seemed the same as the instructions.
At the completion, the phone sat for ages on the apple logo. I thought it was frozen, but I just left it for about 10-15 minutes and it booted up. I'm not sure if this was normal or almost frozen or a dodgy tethering lead (I suggest you use a tehering lead that's new and confirmed as working well). I did play with the lead so maybe I just had a bad connection.
That was all I did and it worked for me. Read my notes as they need to be done in order and some aren't that clear in the instructions.