I know you've said you are, but are you SURE the phone is locked to O2? How have you verified this? It's just that apple stores are pretty much the only place you can get iPhones that don't lock to their first network. You also say it was a donation to an auction at an apple store, but maybe it came from somewhere else?!
The only other thing I can think of is maybe it's a faulty SIM or not yet fully activated. Activations have been slow over the last couple of days due to that pesky christmas thing If you only joined yesterday, this is quite likely. Can you try the SIM in another unlocked phone to verify it works. That would be helpful in solving this
Hope that helps