I second the colored background black or white text plan. Pretty much any scheme for creating contrast will either fail for grey (as the 255-r,255-g,255-b method does), produce eye-destroying combinations, or have at least one of the colors so close to white/black that it's not worth the effort to calculate it (like my idea, using HSB to create a complimentary pair, one color with high brightness and low saturation and the other vice-versa, aka a pastel and and an earthtone).

I do, however have to take issue with your luminance function. Those coeffiecients are for NTSC, and despite the fact that it would likely never make a difference, for the sake of argument

Y = 0.212671 * R + 0.715160 * G + 0.072169 * B

is more apropriate for a computer monitor.

Having worked off and on with L*a*b* and L*u*v* transforms for several months now, I whole heartedly agree that it's not in any way worth pursuing them. 'Uniformly distributed' in either is easier said than done, as neither a* and b* nor u* and v* have well defined maximums. Now call me crazy, but color spaces that let you specify colors outside the gamut of *light* bother me.