I'm having this same issue. I can install the 5.0 and 4.3 simulators, and have done so. I have been able to successfully build apps targeting all three simulators: 4.3, 5.0 and 6.0 - but still cannot install the 5.1 simulator. Any attempt is greeted with the "does not have access to iOS 5.1 Simulator" message.
The 5.1 simulator worked in the previous Xcode (4.4.x), so I'm unclear what sort of access I'm required to have.
I've logged in to the developer account center, couldn't find any new license agreements to approve - pretty sure I've already done this. Like 3rland above, I do not yet have a paid developer account. However, a paid account was not necessary before. Seems strange to limit access to the 5.1 simulator, when 4.3, 5.0 and 6.0 are all accessible.
I've even been able to install the Command Line tools.