I just got a replacement yesterday. It's a week 28 iPhone which to my surprise came with 4.0 installed. My first one was a week 30 that shipped with 4.0.1. The genius had to go in the back of the store to get some new black boxes to put up front when he was getting mine, so some stores must still have new phones as replacements.