Do you have their number set as an iPhone in your contacts list? If that is the case, I believe the red means they don't have iMessage either because it is not set up or possibly because they don't have an iPhone. Try changing their phone type from iPhone to mobile/cellphone/home/something else and see what happens.