I wouldn't be keen on random systems with the only element of 'real stars' being the idea of naming them based on order of proximity. That is almost the same as random stars. The whole point of real stars is using the actual mass and spectral class of each star and having them in the correct xy direction.
You can do better than that: just randomize positions, and assign real names and properties according to distance. This way, you get plausible distances, correct class, mass and names.
I believe you could even change the bearings to their correct value (in your 2D projection system, that is). Such random corrections would not change overall density.
To summarize, the procedure would be :
1- generate a random set of nameless, massless and classless stars, according to some prior density (controlled by game parameters)
2- sort the systems according to their distance to the sun, and associate each one with a real star, thus determining name, class and mass
3- change the bearing of those stars, to match those of their real namesakes (therefore maintaining the constellations in order, a good thing since many stars are named from their constellation)
I haven't done the maths, but I believe that so long you don't change the distances from step one, you remain in line with the original density.
Francois