I'm curious why plastic tube sleeves wouldn't be acceptable given that red and yellow fluorescent lamps tend to be colored anyway. Due to the visible blue light produced directly by the discharge it's not practical to make a saturated red or yellow otherwise (there are some reds that are white when unlit, but those appear very pinkish when lit).
Here are a few for sale. The top two are 40W T12. If you can use 36W T8, there are more options. The T8 lamps will fit in the same fixture and should be fine provided there's no reason a narrower diameter would be prohibitive and that the ballast supports them (most preheat and electronic T12 ballasts will, North American rapid start and European SRS will not).
ATR Lighting 4' 40W RedInterlight 4' 40W Yellow/GoldInterlight 4' 36W Yellow/GoldLightbulbs.com 4' 36W RedBulbs.com 4' 36W Yellow/Gold (pack of 4)