I have been following this discussion since last week as I had the exact same issue. Unfortunately Vigin don't do a micro sims in the uk for the iPhone 4 & 4's, but we just used scissors. My Mum cut her sim months ago for her iPhone 4, all worked fine, no issues touch-wood. I decided i would just do the same when i got my iPhone 4s. I done the whole launch day thing and within two hours i had the iPhone 4s 32GB in White. Once home we cut up my sim, for 5 minutes all was fine and then 'Sim Fauilure' message appeared, followed by invalid sim. After turning the phone on/off several times, yet the same thing kept happening. I then tried my sim in the iPhone 4 and all worked but yet failured in my 4s. I also tried the sim from the iPhone 4 and the exact same thing happened. I reluctantly ordered a replacement sim, which costs a fiver each time, thanks Virgin! While i was waiting i ordered a free 3 PAYG Micro sim from their website, which turned up before my Virgin sim (irony) The 3 sim worked ok, no sim failure, nothing. Now and again the 3G would run incredibly slow or not load after spinning the activity wheel for minutes. I decided it must be Virgin, yes i did call them a few names for making my sim fail. Days later i recieved my new virgin sim, the replacement one. I turned it into a micro sim using scissors, all was ok for 7 minutes, hmm improvment by 2 minutes, result! It turned into Friday the 14th October all over again, the exact same things happened. Both virgin sims would not work but worked in the iPhone 4, both sims failured in my phone in minutes but were fine in the iPhone 4. I was then speaking to my cousin, who is much more intelligent and tech savvy than me, we went through this discussion page seeing what helped others. We tried, rebooting, restarting, reseting the newtwork settings, sim in and out, the lot. We then tried a restore as we honestly thought it would help, sure enough it did.... for 4 hours and then Sim failure and back to square one. During this time i realised there was some other things going on like my wi-fi sync through iTunes would work once and then you try to do it again and get an error message along with your device being removed from iTunes. The battery was lasting a couple of hours, even though 3G was off, forced close all apps and wasn't even using my phone as i was getting bored of the lack of things to do without a sim and completely frustrated. There was a list of 5/6 things that i couldn't blame all on virgin. On Wednesday 26/10 I took my iPhone 4s back to the Apple store, the same store it was purchased at on Launch day, which might i add was amazing and believe everyone should experience it at least once. I explained all to the Apple guy, he gave some reasons but said i would need an appointment with a genuis, which unfortunately we couldn't go back for in 4 hours time, he then said there is enough wrong with it and as I'm in the 14 day period he could replace it with a new one, which he did. No drama, nothing. All very pleasant. He then put my Virgin sim in my phone and started the set-up process. So far A full 48 hours later all is fine and dandy, no sim failure messages, nothing. Everything seems to be great (again) touch-wood.
However, i do have a slight issue with iCloud. As soon as i try to set up my emails from my mobileme account and get the 'this address is already registred with iCloud,' which I'm fully aware of as it's me, and i done it back on the 14th but for some reason it just will not allow me to set up, which is a tad frustrating but on the brighter side, this iPhone 4s is working and touch-wood that it stays like that.