For a Birthday field using the Date module, Views sorts it by year. This puts the dates in basically random order once you format it to display only the month and the day. Could it sort by day and month only?
Extra bonus question: Could Views sort the Birthdays in context of the current day so the upcoming Birthdays float to the top?