Hm, I should have been more specific.
I do indeed see the date in the format I want on the lockscreen, but in the contacts the birthday shows up as 12-8-2012. Strangely enough, if I edit the birthday and remove the year, it then shows up as December 8. Odd.
I guess that's the only place it shows up this way, every other places seems ok so far.