Please try printing a demo page from the printer, and see if you get any color on that. To do this, press the Left and Right arrows on the printer control panel simultaneously.
See this page for other useful reports, such as a supplies report also.
Let me know if the printer will print these in color. If it does, then your printer is probably configured to print in greyscale in the printer properties. You can open the printers and faxes, or devices and printers folder on your computer. Then right click on the printer and choose printer preferences or properties. Go into the printing preferences and make sure it is set to print color and not greyscale.
You can also check the printer properties in the application after you push the print button to make sure it is set to print color.
That sounds like you got a defective magenta cartridge. It is pretty rare, but I have seen it happen. I would first remove the magenta cartridge, then shake it side to side 4-5 times to distribute the toner. Replace the magenta and try to print something with red again. If it still doesn't print, you will need to return the cartridge for a replacement.
I have discovered that you have a common problem. Here is a link to a post on the problem, there is a pdf file at the bottom of the page with some instructions on taking it apart. You may need to get the printer serviced if you are not comfortable doing this, or you can have a Black and White Laserjet. :) Your printer should have a 1 year warranty, though I imagine that is already past if you are experiencing this problem.