If a day/month pair is tricky (I don't know whether it is or not) why not have a field of "their birthday in 1980" (whether they were alive then or not). Then you just need to do the search against 1980. This is effectively a day/month pair, but stored in a type you can use easily.
Note that 1980 is a leap year, which is why I chose it - otherwise those with a birthday of February 29th could be hard to represent.
Alternatively, a "day/month" pair in the form of an integer:
(100 * month) + day
would give you a simple representation which would be easy to search and index. I've usually found that storing data in a single field is simpler than using two fields. Then again, I've never used Solr...
EDIT: I've had another idea. It's a bit balmy, but even so...
Store the birth date in a format which is effectively month, day, year. I don't know if Solr could easily do it in MM/dd/yyyy format and then do a lexicographic order search, but the alternative is
(100000 * month) + (1000 * dayOfMonth) + (year - 1900)
(This is assuming you don't need it to store birth dates earlier than 1900. I'm sure you can tailor it.)
You can still recover the original birth date, but the ordering will be in birthday order, with the oldest person first for any particular date.
It does mean it's hard to sort people by their actual age though. I don't know if that's an issue for you.
Anyway, as I said it's a bit off-the-wall, but it might help :)