If you take a look at the Hertzsprung-Russell Diagram that helps us to classify stars
(c) Wikimedia commons
(while this one uses data gathered from the Hipparcos satellice, roughly 100.000 stars) we see, that there are 2 main types of red stars: Giants and M-dwarves. The latter are stars on the main sqeuence (they have stable hydrogen-burning in their cores), while the giants are stars that have left the main sequence due to aging. They appear red as they bloat up to bigger radii compared to their main-sequence life which also makes them cooler, and thus redder.
Betelgeuse is now one of those giants, and he's actually more massive than the sun (somewhere between 7 and 20 solar masses, according to wikipedia), so there is no contradiction with M-Dwarves also being red.
Please let me know if you desire to know more details on this.