Ok, long story short. I bought the iphone 3G off a friend who has just got the iphone 3GS. He had it on contract and I wanted PAYG. As with previous contract phones I've had, they seem to work fine when you put a PAYG SIM card in them.

However, I've put my PAYG SIM in the iphone i've got (Text Anytime tarriff), and nothing is happening. It comes up with 'Waiting for activation' but this goes on forever. It shows 02-UK in the top left but no signal. I was told to go to Settings > General > Network > Cellular Data Network and change the APN on Cellular Data and MMS to payandgo.o2.co.uk, but still nothing.

I've also tried unlocking/jailbreaking the phone with redsn0w but I just keep getting stuck on 'Downloading Jailbreak Data', then it just reboots. Nothing.

Can anyone help me out here?

Alright. First things first.

We need a little bit more information from you.

#1 What's your phone's baseband version?
Go to Settings > General > Info, scroll all the way down. Tell us the Modem-Firmware.

#2 Are you a PC or a Mac?

#3 Did your friend get the phone with a contract, e.g. is the phone locked to an official carrier?

So long...

#1 Modem-Firmware is 05.11.07

#2 PC

#3 Yes he got the phone on cotract with O2. I have brought an O2 PAYG SIM which I assumed would be ok to use straight away.

Alright. Well, you're already on the latest Modem-Firmware 05.11.07, which you can't unlock as of now to use with another SIM.

The iPhone Dev Team is looking into this but nobody knows when or if an unlock will be possible.

There are, nevertheless, some options for you:

Since you are using a PAYG SIM of the same carrier (O2) it might work.
I can't assure you anything though!
You can't just switch SIMs with the iPhone and be happy.
When your phone says 'Waiting for activation' you are actually supposed to hook it up to your PC and fire up iTunes, cause that's required for activation.
Anyways, I would do a fresh restore to 3.1 with your SIM inserted and see if it gets activated through iTunes.

If not there is one more chance for you:

Download official 3.0 for iPhone 3G here.
Connect the iPhone to your PC and fire up iTunes. Now shift-click Restore and choose the file you just downloaded.
Once done, use redsn0w to jailbreak.
Start up Cydia on your iPhone and search for 'Fuzzyband'. Install Fuzzyband. This piece of software tells you if your iPhone's baseband can be downgraded.
Depending on how old your phone is, you have bootloader 5.8 or 5.9. With 5.8 you're lucky and able to downgrade your baseband.
If you are able to downgrade do so with Fuzzyband. You should be on Modem-Firmware 04.26.08 after the process and now able to run ultrasn0w from Cydia to unlock your phone.

Hope this helps. Good luck!

I already did the restore with my SIM in it. It has activated on itunes. All my info has come up including my PAYG phone number. However, all I still get is O2-UK in the top left and no signal. Not sure why this is.

I downloaded the 3.0 and hit shift-restore and an error came up saying "unknown error occured (1015)".

I'm not having much luck.

Try restoring to 3.0 in DFU mode.
Quit iTunes. Plug your iPhone into USB and turn it off.
Now press and hold power and home buttons simultaneously for 10 seconds.
Release the power button and keep holding the home button for another 10 seconds.
The timing needs to be exact (use a watch or something)!
Start up iTunes, it should now detect an iPhone in recovery mode.
Again shift-click restore and choose the downloaded 3.0 .ipsw.

The error still came up.

Hmm...
I think I can't help you any further. But let me refer you to this thread at modmyi.com:
Have error 1015? It has you: Stuck? Confussed? READ THIS.
This is about error 1015 ONLY!

Another really useful downgrading tutorial is here:
My Successful Downgrade [3.1 to 3.0 on 3G] WITH Carrier Network (Canada>Rogers-Fido)

I hope this helps you in any way.
Keep it up.

No worries. Sorted. I simply ignored the error and ran redsn0w anyway. I read somewhere that you should ignore this message as it just means 3.0 is successfully installed. Finally Success!

Anyone else having this problem, this should help.

How to Downgrade iPhone OS 3.1 to 3.0 for iPhone 2G 3G 3GS | iPhone