In the same situation..
Ordered from CPW online on the 7th (day released to preorder). All went fine until the phone was delivered (no need to ring up/hassle CPW), then Apple played up for ~1hr and couldn't activate in itunes. Once that finally succeeded, I'm stuck in 'No Service'.
I called CPW on Saturday, who told me it was an O2 issue and put me through to O2. O2 told me that they knew there was a problem, but it would all be sorted by 5pm on Saturday.
It wasn't, so called up O2 on Sunday, and was told that it would be activated 'by the end of Sunday'.
It wasn't, so I rang up today to be told that O2 have no record of me, no record of my phone number, and have absolutely no idea when I will be activated. Apparently someone will ring me in the next hour (at 11am, I was told I'd be rung within 5 hours to sort it out), but I doubt it somehow.
I can get that a systems failure could seriously mess something like this up, but I dont like being systematically lied to me - if someone tells me something will happen, then it bloody well should be, or they should contact me to tell me why they haven't done what they said they would.
I also don't get this 'massive demand killed our systems, its not our fault' angle. They knew how many iphones they were getting, they knew how many people registered an interest. Putting two and two together, they should have anticipated that if they have N iphones coming in, they should have realistically expected to have been able to activate N contracts.
I hope by the time they release the next iphone, apple will have wised up and allow all operators to sell them. iphone on vodafone would have been nice.