I've quickly made a vertex/fragment shader that successfully interpolates the colors:
#ifdef GL_ES
precision highp float;
#endif
uniform vec2 resolution;
void main(void)
{
    vec2 p = gl_FragCoord.xy / resolution.xy;
    float gray = 1.0 - p.x;
    float red = p.y;
    gl_FragColor = vec4(red, gray*red, gray*red, 1.0);
}
Here's the result:

Applying it on a quad now yields the correct result because the interpolation is truly done over the entire surface using x and y coordinates. See @datenwolf's detailed explanation as to why this works.
EDIT 1 In order to obtain the full range of colors in a functional color picker, it is possible to modify the hue interactively (see https://stackoverflow.com/a/9234854/570738).
Live online demo: http://goo.gl/Ivirl
#ifdef GL_ES
precision highp float;
#endif
uniform float time;
uniform vec2 resolution;
const vec4  kRGBToYPrime = vec4 (0.299, 0.587, 0.114, 0.0);
const vec4  kRGBToI     = vec4 (0.596, -0.275, -0.321, 0.0);
const vec4  kRGBToQ     = vec4 (0.212, -0.523, 0.311, 0.0);
const vec4  kYIQToR   = vec4 (1.0, 0.956, 0.621, 0.0);
const vec4  kYIQToG   = vec4 (1.0, -0.272, -0.647, 0.0);
const vec4  kYIQToB   = vec4 (1.0, -1.107, 1.704, 0.0);
const float PI = 3.14159265358979323846264;
void adjustHue(inout vec4 color, float hueAdjust) {
    // Convert to YIQ
    float   YPrime  = dot (color, kRGBToYPrime);
    float   I      = dot (color, kRGBToI);
    float   Q      = dot (color, kRGBToQ);
    // Calculate the hue and chroma
    float   hue     = atan (Q, I);
    float   chroma  = sqrt (I * I + Q * Q);
    // Make the user's adjustments
    hue += hueAdjust;
    // Convert back to YIQ
    Q = chroma * sin (hue);
    I = chroma * cos (hue);
    // Convert back to RGB
    vec4 yIQ   = vec4 (YPrime, I, Q, 0.0);
    color.r = dot (yIQ, kYIQToR);
    color.g = dot (yIQ, kYIQToG);
    color.b = dot (yIQ, kYIQToB);
}
void main(void)
{
    vec2 p = gl_FragCoord.xy / resolution.xy;
    float gray = 1.0 - p.x;
    float red = p.y;
    vec4 color = vec4(red, gray*red, gray*red, 1.0);
    adjustHue(color, mod(time, 2.0*PI));
    gl_FragColor = color;
}
EDIT 2: If needed, shaders for use with texture coordinates (to apply on quads with texture coordinates from 0 to 1) should look something like this. Untested.
Fragment shader:
void main(void)
{
    vec2 p = gl_TexCoord[0].st;
    float gray = 1.0 - p.x;
    float red = p.y;
    gl_FragColor = vec4(red, gray*red, gray*red, 1.0);
}
A passthrough vertex shader:
void main()
{
    gl_TexCoord[0]=gl_MultiTexCoord0; 
    gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex;
}