The crux of your problem appears to be this error: "no matter what, you will not get red (this is proven by the way, you will never get a colour from a bird that wasn't in it originally)."
That is simply not true.
The coloration of bird feathers doesn't work the way you would normally think it does. With most things, like skin, fur, flower petals, etc... the coloration is due to pigments that produce particular colors. However, in feathers the color is not only due to pigmentation but also due to refraction. The size of air pockets within the barbs on feathers control the specific wavelength of light produced. This means that a slight change in the size of air bubbles can produce a variety of colors, from green to blue, and even into the ultraviolet range.
If you take a look at a blue jay's feathers, for example, you will find no blue pigment at all. The color is simply a product of light diffraction, like the colors from a prism, but only a specific part of the spectrum.
Still, we're talking about the color red. Red is produced by the pigments called carotenoids, the same thing that colors carrots (hence the name). Actually, carotenoids can produce colors from red to orange to yellow. In other words, the pigment that makes yellow in one species is the same pigment that makes in red in the other. See:
http://www.birdersworld.com/brd/default.aspx?c=a&id=667
So, you have a common ancestor for both species it could have had some or all of the traits found in both of the species that descended from it. Furthermore mutations, genetic drift, and natural selection could have produce all of the changes since then. This wasn't something that happened overnight, but over hundreds of millions of generations.
Furthermore, it often only takes a single mutation to make a single new color. For example, the allele that produces blue eyes in humans is apparently a relatively new mutation that first appeared 6,000 to 10,000 years ago. Apparently people found blue eyes attractive, because the allele spread, and is the source for every blue eyed person alive today. See:
http://www.sciencedaily.com/releases/2008/01/080130170343.htm
Finally, while any animal will normally only give birth to offspring with only tiny changes from the parents, if you accumulate changes across many many generations the descendants will often be quite different from their ancestors. Large scale evolution of animals usually takes far too long for humans to see in their lifetimes, but the fossil, genetic, morphological, and geographic evidence all support that these species, and all others, most likely evolved from a common ancestor, even though they now have visible differences.
Hope that helps! :-)